【 分数和判断 】 Fractions Again

传送门

题意

给定(k)，求出正整数(x,y)满足(frac{1}{k}=frac{1}{x} + frac{1}{y})，且(xgeq y)

数据范围

(0leq kleq 10000)

题解

• (frac{1}{k} = frac{1}{x} + frac{1}{y})
• (frac{1}{x} = frac{1}{k}-frac{1}{y})
• (ecause xgeq y, herefore frac{1}{x}leq frac{1}{y})
• ( herefore frac{1}{x} = frac{1}{k}-frac{1}{y} leq frac{1}{y})
• ( herefore frac{1}{k} leq frac{2}{y})
• ( herefore y leq 2cdot k)
  在(k+1 sim 2cdot k)范围内进行枚举即可，
  可以通过(gcd)判断，也可以直接通分后判断(x)的值是不是整数即可

Code

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
typedef pair<int,int>pii;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int k;

int main(){
    while(scanf("%d",&k)!=EOF){
        vector<pii>rec;
        rep(y,k+1,2*k){

            int down=k*y;
            int d=gcd(up,down);
            if(up%d==0 && up/d==1){
                rec.push_back({down/d,y});
                
            }
            // if(k*y%(y-k)==0) rec.push_back({k*y/(y-k),y});
        }
        printf("%d
",rec.size());
        for(int i=0;i<rec.size();i++)
            printf("1/%d = 1/%d + 1/%d
",k,rec[i].first,rec[i].second);
    }
}