题目描述
输入
2 12
输出
2 1/2 = 1/6 + 1/3 1/2 = 1/4 + 1/4 8 1/12 = 1/156 + 1/13 1/12 = 1/84 + 1/14 1/12 = 1/60 + 1/15 1/12 = 1/48 + 1/16 1/12 = 1/36 + 1/18 1/12 = 1/30 + 1/20 1/12 = 1/28 + 1/21 1/12 = 1/24 + 1/24
思路: 由于没有给x,y的数的范围,也不知道啥时候枚举结束.我们可以根据已知条件做出一些推断:
1/k = 1 / x + 1 / y <= 2/y ===>> y<=2*k
另外x = k*y / (y-k) => y>k
所以 y∈[k+1,2*k]
这样我们粗略的得到了y的范围,知道了y的范围,我们可以根据上面那个式子推出x ,在判断x是否存在时,我们可以通过 求余进行判断推出的x是否合理.
参考代码:
#include<iostream> using namespace std; int k,y,a[5000],b[5000],cnt;//定义两个数组存储所有的可能性. int main() { //y<=2*k x = k*y / (y-k)==> y >k while(cin>>k){ //memset(a,0,sizeof(a)); cnt = 0;//用于计数 for(int y = k+1; y <= 2*k;y++){//枚举y,同时枚举x if(!(k*y % (y-k)) && k*y / (y-k) >=y){//当 k*y 对 (y-k)求余为0,并且x >=y 则说明满足题意. a[cnt] = k*y / (y-k); b[cnt] = y; cnt++; } } cout<<cnt<<endl; for(int i = 0;i < cnt;i++){ printf("1/%d = 1/%d + 1/%d\n",k,a[i],b[i]); } } return 0; }
另外看了看刘汝佳大佬的代码,也很不错,附上
参考代码2
#include<iostream> #include<cstdio> #include<vector> using namespace std; int main() { int k; while(scanf("%d",&k)==1&&k){ vector<int> X,Y; for(int y = k+1;y<=2*k;y++){ if(k*y %(y-k)==0){ X.push_back(k*y /(y-k)); Y.push_back(y); } } printf("%d\n",X.size()); for(int i = 0;i < X.size();i++){ printf("1/%d = 1/%d + 1/%d\n",k,X[i],Y[i]); } } return 0; }
