首页 > 代码库 > （数论）最大公约数和最小公倍数问题
（数论）最大公约数和最小公倍数问题
题目描述 Description
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数
条件: 1.P,Q是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
输入描述 Input Description
二个正整数x0,y0
输出描述 Output Description
满足条件的所有可能的两个正整数的个数
样例输入 Sample Input
3 60
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
3 60
60 3
12 15
15 12
思路：y/x然后分解质因数然后2的次幂就是答案。
1 #include<stdio.h> 2 #include<math.h> 3 int x,y; 4 bool zhi(int x) 5 { 6 for (int i=2;i<=sqrt(x);++i) 7 if (x%i==0) return 0; 8 return 1; 9 }10 int main()11 {12 scanf("%d%d",&x,&y);13 if (y%x!=0)14 {15 printf("0/n");16 return 0;17 }18 x=y/x; y=0;19 for (int i=2;i<=x;++i)20 if (zhi(i))21 { 22 if (x%i==0) ++y;23 while (x%i==0) x/=i;24 }25 printf("%d/n",(int)pow(2,y));26 return 0;27 }
（数论）最大公约数和最小公倍数问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。