【暴力】分数拆分 UVa 10976

题目:给你一个数k,求所有使得1/k = 1/x + 1/y成立的x≥y的整数对。

分析:这个题显然要用暴力求解,但是暴力的最大数量是可以计算的。

   x≥y,所以y的最大值应该为k的2倍,确定范围之后对y开始枚举就可以了。把式子通分,可以求得x = [k * y / (y - k)], 这里要求y必须大于k,所以枚举时y的范围可以进一步缩小为[k+1, 2*k]。

   对y进行枚举,判断k*y%(y - k)这个式子是否为零,如果为零,说明此时算出的x为正整数,而这个x也正是符合题意的x。

 1 #include<bits/stdc++.h>
 2 int main()
 3 {
 4     int k, x, y;
 5     while(scanf("%d",&k) == 1)
 6     {
 7         int a[10007], b[10007];
 8         int i = 0, j;
 9         for(y = k + 1; y <= 2*k; y++)
10             if((k * y) % (y - k) == 0)
11             {
12                 x = (k*y)/(y-k);
13                 a[i] = x;
14                 b[i] = y;
15                 i++;
16             }
17         printf("%d
",i);
18         for(j = 0; j < i; j++)printf("1/%d = 1/%d + 1/%d
",k,a[j],b[j]);
19     }
20     return 0;
21 }
原文地址:https://www.cnblogs.com/Kohinur/p/8523183.html