题解 P1029 【最大公约数和最小公倍数问题】
ouuan
2018-01-06 18:43:20
基本思路其它题解已经说的很清楚了，主要是利用质因子个数算和直接遍历两种方法
大概看了一下前两页题解，发现很多用后者做的人都是直接遍历一半然后乘2
这样的话如果有x0==y0的数据就会WA（只不过这题没有）
还是大致说一下思路，(p,q)\*[p,q]==x0\*y0，所以从x0到sqrt(x0\*y0)遍历p，gcd(p,x0\*y0/p)==x0时符合要求，题目问的是p和q所能取到的不同值个数，所以ans+=2。但如果x0==y0只有p==q一种情况，应该输出1。
```cpp
#include <iostream>
using namespace std;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int x0,y0,p,ans=0;
cin>>x0>>y0;
if (x0==y0) //x0==y0则直接输出1
{
cout<<1;
return 0;
}
for (p=x0;p*p<=x0*y0;p+=x0) //用p*p避免sqrt（只不过会增加完全可以忽略的时间开销）
{
if ((x0*y0)%p==0&&gcd(p,x0*y0/p)==x0)
{
ans+=2;
}
}
cout<<ans;
return 0;
}
```