首页 > 代码库 > UVa10976 - Fractions Again?!

UVa10976 - Fractions Again?!

题意

输入正整数k,找到所有的正整数x >= y,使1/k = 1/x +1/y。

思路

先找到x或y的范围:因为x >= y,所以 1/k <= 2/y 得出 y<=2*k

再找到可以计算出x的方法即可

总结

刚开始用了二重循环找x,结果超时。今天早晨起来想了个更常规且更简单的方法

 1 #include <iostream> 2 #include <cstdio> 3 const int maxn = 1e6+5; 4 typedef long long LL; 5 using namespace std; 6 LL a[maxn],b[maxn]; 7 int main() 8 { 9     LL k;10     while(scanf("%lld",&k) == 1) {11         LL cnt = 0,kk = 2*k,x,y;12         for(LL y = k+1; y <= kk; y++) {13             if(y*k%(y-k))14                 continue;15             LL x = y*k/(y-k);16             if(x >= y) {17                 a[cnt] = x;18                 b[cnt++] = y;19             }20         }21         cout<<cnt<<endl;22         for(int i = 0; i < cnt; i++)23             printf("1/%lld = 1/%lld + 1/%lld\n",k,a[i],b[i]);24     }25     return 0;26 }

 

UVa10976 - Fractions Again?!