P1029题解

Nahia · 2025-02-13 15:42:17 · 题解

思路

因为两个数的积等于它们最大公约数和它们最小公倍数的积，即：

从 1 到 \sqrt[]{x_0 \times y_0} 枚举 P，逐个判断有没有满足第一个条件的 Q，再带着 P 和 Q 判断一下能不能满足后面的两个条件。（注意：对于 P 和 Q 两个数不同的情况，交换这两个数也一定能得到另一组解）

注：

• 可以使用 C++ 自带的函数 __gcd() 来求最大公倍数 \gcd。

• 如果 P = Q，易得 P = Q = \gcd(P,Q) = \operatorname{lcm}(P,Q)，只有一种情况，但是这种情况只有在 x_0 = y_0 时会出现，所以特判一下就好了。

solution

#include<bits/stdc++.h>
using namespace std;
int x,y,ans;
int main(){
    cin>>x>>y;
    if(x==y) ans--;
    y*=x;
    for(int i=1;i<=sqrt(y);i++){
        if(y%i==0&&__gcd(i,y/i)==x) ans+=2;
    }
    cout<<ans;
    return 0;
}