Uva 10976 Fractions Again?

题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1917

题意:给定k,寻找满足1/k=1/x+1/y(x\geq y)xy

思路:等式变形一下得到x=\frac {k*y}{y-k},又因为x \geq y,解不等式可以得到y\leq 2*k,枚举y即可。

#include <bits/stdc++.h>
using namespace std;
int n,x,y;
vector<pair<int,int> >vec;
int main(){
    while (~scanf("%d",&n)){
        vec.clear();
        int cnt=0;
        for (int i=n+1;i<=2*n;i++){
            if ((i*n)%(i-n)==0){
                x=i;
                y=i*n/(i-n);
                if (x<y) swap(x,y);
                vec.push_back(make_pair(x,y));
                cnt++;
            }
        }
        sort(vec.begin(),vec.end());
        printf("%d\n",cnt);
        for (int i=cnt-1;i>=0;i--){
            printf("1/%d = 1/%d + 1/%d\n",n,vec[i].first,vec[i].second);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注