问题描述
输入格式
输出格式
样例输入
3 60
样例输出
4
提示
数据范围
题解
我们知道p*q=gcd(p,q)*lcm(p,q)
题目已知gcd和lcm，即x0和y0，由此可得到p*q的值。那么只要枚举p，就能得到q=x0*y0/p
由于q是整数，所以p一定是x0*y0的因数
从2开始枚举p，若p是x0*y0的因数且gcd(p,q)=x0，则p为满足条件的一种方案
然而为什么还要满足gcd(p,q)=x0,或者为什么只需满足gcd(p,q)=x0而不需要lcm(p,q)=y0?
因为若能找到一个p是x0*y0的因数，必能得到一个q，使得p*q==x0*y0,但事实上乘积相同的两个数有很多组（例如2*9=3*6=18），有可能我们找到的这组p，q并不是满足gcd(p,q)=x0,lcm(p,q)=y0的那组，所以我们求出来的p，q还需要满足gcd(p,q)=x0。那么为什么不需要再满足lcm(p,q)=y0呢？因为我们已知gcd(p,q)*lcm(p.q)=p*q=x0*y0,所以只要满足gcd(p,q)=x0,就可以知道lcm(p,q)=y0一定成立
由样例可知，每一组数总能找到与之相对应的顺序相反的另一组数（3,60和60,3两个数字完全一样只是顺序不同）事实上，一个数的因数是关于它的平方根对称的，即i和n/i一定一个小于sqrt(n)一个大于sqrt(n),那么只要从2枚举到平方根，找到所有满足条件的数，最后结果乘2即为答案
1 #include <cstdio> 2 #include <cmath> 3 int x,y; 4 int gcd(int a,int b) 5 { 6 return b?gcd(b,a%b):a; 7 } 8 int main() 9 { 10 scanf("%d%d",&x,&y); 11 if (x==y) 12 { 13 printf("1"); 14 return 0; 15 } 16 long long n=1ll*x*y,m=sqrt(n); 17 int i,s=0; 18 for (i=2;i<m;i++) 19 if (!(n%i) && gcd(i,n/i)==x) 20 s++; 21 printf("%d",s*2); 22 return 0; 23 }