解题报告 P1029 gcd 和 lcm 问题

题目内容

P1029

大意：给出 x_0, y_0 ，求出满足 \gcd(P,Q)=x_0,\operatorname{lcm}(P, Q)=y_0的 P,Q 的个数

解题思路

挨个枚举即可，从 x_0 枚举到 y_0 ，具体思路是以下关系：

\gcd(a,b)\times\operatorname{lcm}(a,b)=\lvert ab\rvert

算出枚举到的 \gcd 然后用 x_0y_0 去除判断 lcm 是否符合条件即可。这题的数据范围理论上可以爆 int 但是他没有爆。管他的代码规范最重要。

下面的代码可以优化，但是我不想再优化了，老是 WA

#include <cstdio>
#include <cmath>
typedef unsigned long long ll;

ll gcd(ll x, ll y)
{
    if(!y) return x;
    return gcd(y,x%y);
}

int main()
{
    ll x0,y0;
    scanf("%llu %llu",&x0,&y0);
    ll prod=x0*y0,ans=0;//x_0y_0
    for(ll i=x0;i<=y0;i++)
    {
        if(!(prod%i))
        {
            ll gcdcur=gcd(i,prod/i);
            if(gcdcur==x0 && prod/gcdcur==y0)
                ans++;
        }
    }
    printf("%llu\n",ans);
    return 0;
}