首页 > 代码库 > 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?!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。