UVA10976-Fractions Again?!【枚举】

链接

Fractions Again?!

思路

因为 $\frac{1}{k}-\frac{1}{x}=\frac{1}{y}$，又因为 $x\geq y$，所以 $\frac{1}{k}-\frac{1}{y}\leq\frac{1}{y}$，即 $y\leq2k$，枚举y判断x即可。

代码

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxn = 2e5+10;
const int mod = 1e9+7;int a[maxn];int main(void){int k;while(cin>>k){int cnt = 0;for(int y = k+1; y <= 2*k; y++){int a1 = k*y;int a2 = y-k;if(a1%a2==0) cnt++;}cout<<cnt<<endl;for(int y = k+1; y <= 2*k; y++){int a1 = k*y;int a2 = y-k;if(a1%a2==0){int x = a1/a2;printf("1/%d = 1/%d + 1/%d\n",k,x,y); }}} return 0;
}