P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题——题解

解题思路

若 $y_0$ 不是 $x_0$ 的倍数，答案为 0。否则令 $P=x_0a,Q=x_0b$，则要求 $\gcd(a,b)=1$ 且 $ab=y_0/x_0=k$。为了互质，$k$ 的每一种“完整质因子幂”必须整体分配给 $a$ 或 $b$。若 $k$ 有 $t$ 种不同质因子，每种有两种去向，答案为 $2^t$。

正确性说明

将共同因子 $x_0$ 提出后，最大公约数为 1 要求 $a,b$ 不共享质因子；最小公倍数条件又要求它们乘积为 $k$。因此每种质因子的全部幂次只能完整放在其中一边，且每种有两个独立选择。

复杂度分析

分解 $k$ 的时间复杂度 $O(\sqrt k)$，空间 $O(1)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long x,y;cin>>x>>y;
    if(y%x){cout<<0<<'\n';return 0;}
    long long k=y/x;int cnt=0;
    for(long long p=2;p*p<=k;p++) if(k%p==0){cnt++;while(k%p==0)k/=p;}
    if(k>1)cnt++;
    cout<<(1LL<<cnt)<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ long long x,y;cin>>x>>y; if(y%x){cout<<0<<'\n';return 0;} long long k=y/x;int cnt=0; for(long long p=2;p*p<=k;p++) if(k%p0){cnt++;while(k%p0)k/=p;} if(k>1)cnt++; cout<<(1LL<<cnt)<<'\n';return 0; }