学步园

题目地址

题意:给定一个分数b / a求有多少组整数x,y,满足1 / x + 1 / y = b / a

做法: 把式子转化一下变为 (bx - a)(by - a) = a^2
可以简单的证明一下 如果有x满足 a^2 % (bx - a) == 0 则一定存在对应的 y 使(bx - a)(by - a) = a^2成立.
设 x <=y , 那么再根据对称性可得, bx - a <= a.
dfs出所有的a^2小于等于a的因子，验证一下是否满足条件
有b > a的直接无解，陷阱

#include<stdio.h>
#define LL long long
int a,b,cas,p[100],num[100],cnt,ans;
int gcd(int a,int b){ return b?gcd(b,a%b):a; }
inline bool judge(int i)
{
    if((i+a)%b!=0) return false;
    if((1ll*a*a/i+a)%b!=0) return false;
    return true;
}
void getP(int n)//分解n^2素因子
{
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0){
            p[cnt]=i; num[cnt]=0;
            while(n%i==0) num[cnt]+=2,n/=i;
            cnt++;
        }
    }
    if(n>1) p[cnt]=n,num[cnt++]=2;
}
void dfs(int h,LL mul)//枚举因子
{
    if(mul>a) return ;
    if(h==cnt){
        if(judge(mul)) ans++;
        return ;
    }
    LL tmp=1;
    for(int i=0;i<=num[h];i++,tmp*=p[h])
        dfs(h+1,mul*tmp);
}
int main()
{
    cas=1;
    while(scanf("%d%d",&b,&a)!=-1)
    {
        int g=gcd(a,b);
        a/=g; b/=g;
        cnt=0; getP(a);
        ans=0;
        dfs(0,1);
        printf("Scenario #%d\n",cas++);
        if(b>a||ans==0)
            puts("No solution");
        else if(ans==1)
            puts("Only one solution");
        else
            printf("Find %d solutions\n",ans);
        puts("");
    }
}