divisors of 4 are 1, 2 and 4 and the positive divisors of 3 are 1 and 3, so S(4/3) = 1/1 + 2/1 + 4/1 + 1/3 + 2/3 + 4/3 = 28/3. 输入
Each line of input will be of the form a/b (with no white space) where a and b are integers in the range from 1 to 16000. 输出
Each line of output is of the form a/b where a and b are integers, and the fraction is in simplest terms (so 1/2 will be output instead of 2/4 for example). 样例输入 6/1 2/3 100/49 样例输出 12/1 4/1 1767/7 翻译： 描述
在18世纪，L. Euler发明了一个功能去研究数字的特性，他称之为sigma。他对比较整数的正因子的和感兴趣。在这个问题我们扩展Euler的功能到分数。
给一个正分数最简形式a/b，我们定义 S(a/b) 是所有整数x/y的和，x/y是正因子组成，x来自a的因子，y来自b的因子。例如，4的正因子是1 2 4；3的正因子是1 3。所以S(4/3) = 1/1 + 2/1 + 4/1 + 1/3 + 2/3 + 4/3 = 28/3。 输入
每行输入a/b，a b范围1到16000. 输出
每行输出S(a/b)的值，分数最简形式。
思路/方法：
1.定义数组a和b分别存储输入的两个数的因子。 2.定义一个结构体用来表示分数 3.定义一个函数用来计算分数相加
4.把a和b因子组合起来的分数累加起来，然后约分为最简。 不太好说，具体看下面代码，不难。 代码：
#include
typedef struct Fraction//分数 {
int numerator;//分子 int denominator;//分母 }fraction;
int greatestCommonDivisor(int a, int b) {
int t; while(b) {
t = a % b; a = b; b = t; } return a; }
fraction addFraction(fraction * f1, fraction * f2) {
fraction s; int divisor;
if(f1->denominator == f2->denominator || f1->numerator == 0)//两数分母相同 {
s.numerator = f1->numerator + f2->numerator;//分子相加 s.denominator = f2->denominator; } else {
s.denominator = f1->denominator * f2->denominator;//分母通分
s.numerator = f1->numerator * f2->denominator + f2->numerator * f1->denominator;//分子通分后相加 divisor = greatestCommonDivisor(s.numerator, s.denominator);//求最大公约数 //约分
s.numerator /= divisor; s.denominator /= divisor; } return s; }
int main() {
int a[16001], b[16001], i, j, ca, cb; fraction s, t;
while(scanf(\把a和b存到a0 b0 {
ca = cb = 1;
for(i = 1; i <= a[0]; i++)//a的所有因子 {
if(a[0] % i == 0) {
a[ca] = i; ca++; } }
for(i = 1; i <= b[0]; i++)//b的所有因子 {
if(b[0] % i == 0) {
b[cb] = i; cb++; } }
s.denominator = s.numerator = 0;
for(i = 1; i < cb; i++)//计算因子组合的和 {
for(j = 1; j < ca; j++) {
t.numerator = a[j]; t.denominator = b[i]; s = addFraction(&s, &t); }
}
int divisor = greatestCommonDivisor(s.numerator, s.denominator);//求最大公约数 //约分
s.numerator /= divisor; s.denominator /= divisor;
printf(\ } return 0; }
9: 简单组合问题 描述
对于有m个元素的集合，在元素能重复取的情况下，我们可以得到有r组合的集合；例如，当m=2，r=4时，集合{a,b}可以划分为5个不同的r组合的集合: {a,a,a,a}; {a,a,a,b}; {a,a,b,b}; {a,b,b,b}; {b,b,b,b}; 输入
输入数据有多组，每行输入2个整型数据m,r，(0 输出可以划分的集合个数 样例输入 2 4 样例输出 5 思路/方法：题目指明了是组合问题，就是不考虑顺序。 这题输入的数据范围小，说明不是有公式就能得出答案的，需要经过推算。 我们不妨来举个例子来看一下是否有规律。 当m=1是，结果都是1 当m=3，r=4时，假设有a,b,c三种数，a就有5(即r+1)种情况，集合中a的个数可以为0 1 2 3 4。a=0时，就剩下b,c来充满4个位置，这种情况的值与m=2，r=4时的值一样；a=1时，就剩下b,c来充满3个位置，这种情况的值与m=2，r=3时的值一样；a=2时，就剩下b,c来充满2个位置，这种情况的值与m=2，r=2时的值一样；a=3时，就剩下b,c来充满1个位置，这种情况的值与m=2，r=1时的值一样；a=4时，位置充满了，值为1。 通过上面例子我们发现s(m=3,r=4)可以转化成s(m=2,r=4) + s(m=2,r=3) + s(m=2,r=2) + s(m=2,r=1) +1。 同样的，我们推广出来就是s(m,r)=s(m-1,r)+s(m-1,r-1)+s(m-1,r-2)+.....+s(m-1,1)+1。 也就是s(m,r)可以转化成前一行的前r列的和+1。 有了这个规律，我们只要知道第一行，就能退出后面的。 这题用递归会超时，所以我们用递推，具体代码如下。 代码： #include int m, r, i; for(r = 1; r <= 20; r++)//m=1时全部都是1 a[1][r] = 1; for(m = 2; m <= 20; m++) for(r = 1; r <= 20; r++) { for(i = 0; i < r; i++)//循环r次 a[m][r] = a[m][r] + a[m - 1][r - i]; a[m][r] = a[m][r] + 1; } while(scanf(\ printf(\ return 0; } 10: GCD & LCM 描述 Given x and y (2 <= x <= 100,000, 2 <= y <= 1,000,000), you are to count the number of p and q such that: 1) p and q are positive integers; 2) GCD(p, q) = x; 3) LCM(p, q) = y. 输入 There are multiple test cases, each case contains two integers x and y, one line for each test case. 输出 Number of pairs of p and q. 样例输入 3 60 样例输出 4 翻译： 描述 给定x,y(2 <= x <= 100,000, 2 <= y <= 1,000,000)，你要像下面那样计算出p和q： 1) p,q是正整数; 2) GCD(p, q) = x;即p,q的最大公约数是x 3) LCM(p, q) = y.即p,q的最小公倍数是y 输入 输入多组测试数据，每组包含两个整数x y 输出 每组输出满足条件的p和q的组数。 思路/方法： 我们要求p，q可能的组数，先来推一下x y p q之间的关系 最小公倍数=两数之积/最大公约数。也就是y=p*q/x; 所以得到xy=pq (范围：x <= p,q <= y) 因为p和q可以用最大公约数的倍数来表示，即设p=x*n1，q=x*n2。 我们可以得到p*q=x*x*n1*n2=x*y。即n1*n2=y/x。 还可以得到gcd(p,q)=gcd(x*n1,x*n2)=x 因此gcd(n1,n2)=1也就是n1,n2是互质的数 (范围：1 <=n1,n2 <= y/x) 所以，确定n1,n2就确定了p,q，我们只需要知道这样的n1,n2有多少组，就知道有多少组p,q 代码： #include int gcd(int a, int b)//最大公约数 { int t; while(b) { t = a % b; a = b; b = t; } return a; } int main() { int x, y, i, c, s; while(scanf(\ { if(y % x != 0)//如果发现最小公倍数不是最大公约数的倍数，就说明组数为0 { printf(\ continue; } c = 0; s = y / x; for(i = 1; i <= s; i++) if(s % i == 0)//能除尽,因为 n1*n2=y/x=s。这里是用i表示n1，s/i表示n2 if(gcd(i, s / i) == 1)//判断n1和n2是否互质 c++; printf(\ } return 0; } 11: Raising Modulo Numbers(快速取模) 描述 People are different. Some secretly read magazines full of interesting girls' pictures, others create an A-bomb in their cellar, others like using Windows, and some like difficult mathematical games. Latest marketing research shows, that this market segment was so far underestimated and that there is lack of such games. This kind of game was thus included into the KOKODDáKH. The rules follow: Each player chooses two numbers Ai and Bi and writes them on a slip of paper. Others cannot see the numbers. In a given moment all players show their numbers to the others. The goal is to determine the sum of all expressions AiBi from all players including oneself and determine the remainder after division by a given number M. The winner is the one who first determines the correct result. According to the players' experience it is possible to increase the difficulty by choosing higher numbers. You should write a program that calculates the result and is able to find out who won the game. 输入 The input consists of Z assignments. The number of them is given by the single positive integer Z appearing on the first line of input. Then the assignements follow. Each assignement begins with line containing an integer M (1 <= M <= 45000). The sum will be divided by this number. Next line contains number of players H (1 <= H <= 45000). Next exactly H lines follow. On each line, there are exactly two numbers Ai and Bi separated by space. Both numbers cannot be equal zero at the same time. 输出 For each assingnement there is the only one line of output. On this line, there is a number, the result of expression (A1B1 + A2B2 + ... + AHBH) mod M. 样例输入 3 16 4