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

知识点

最大公约数、因数枚举、数论

解题思路

若y不是x的倍数则无解。否则令P=xa、Q=xb，可得ab=y/x且gcd(a,b)=1。枚举ab的较小因子a，检查互素。a与b不同则贡献2个有序对，相同则贡献1。

正确性说明

gcd(P,Q)=x等价于gcd(a,b)=1，而lcm(P,Q)=x·ab。两条件因此与互素因子对一一对应。枚举到平方根覆盖所有无序因子对，再按是否相等恢复有序计数，既不漏计也不重计。

易错点

y<x或不整除时输出0；x=y时答案1；P,Q与Q,P是不同方案。

复杂度

时间O(√(y/x)·log(y/x))，空间O(1)。

参考代码（GNU 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 n=y/x,ans=0;for(long long a=1;a*a<=n;a++)if(n%a==0&&gcd(a,n/a)==1)ans+=a==n/a?1:2;cout<<ans<<'\n';}