P1029 题解

· · 题解

题目传送门

思路

已知对于任何 2 个数 P 和 Q，都满足 \gcd(P,Q)\times\operatorname{lcm}(P,Q)=P\times Q。基于这一点，可以从 1 枚举到 x_0\times y_0，统计 x_0\times y_0 有多少个质因数即可。

然而这样做会超时。又发现对于两质因子为 P 和 Q 的情况，一定也会出现两质因子为 Q 和 P 的情况。于是可以只枚举到 \sqrt{x_0\times y_0}，并将统计出的结果乘 2。注意需要判断 x_0\times y_0 是否是完全平方数，若是，就将答案减 1，因为自身统计了 2 遍。

注意事项

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}

signed main(){
    int n=read(),m=read(),cnt=0;
    bool flag=false;
    for(int i=1;i*i<=n*m;++i)
        if(n*m%i==0&&__gcd(i,n*m/i)==n){
            ++cnt;
            if(i*i==n*m)
                flag=true;
        }
    printf("%lld\n",cnt*2-flag);
    return 0;
}