首页 > 代码库 > codevs 1012 最大公约数以及最小公倍数问题 x
codevs 1012 最大公约数以及最小公倍数问题 x
题目描述 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
首先你要知道一点：
若A×B代表二者的乘积，也就是二者最大的乘积，
如果用A×B除以二者的最小公倍数，就能得到了二者的最大公约数
当然前提是这两个数要是非零的两个整数
最大公约数=A×B/最小公倍数
反过来，最小公倍数=A×B/最大公约数
那么这道题就很简单地做出来了：
方法一：枚举
1 #include<iostream> 2 #include<cmath> 3 4 using namespace std; 5 6 int gcd(int a,int b)//求最大公约数 7 { 8 while(b!=0)//辗转相除法求最大公约数 9 {10 int qwq=a%b;11 a=b;12 b=qwq;13 }14 return a;15 //return b == 0 ? a : gcd(b,a%b);16 }17 18 int main()19 {20 int x,y;21 cin>>x>>y;//输入最大公约数以及最小公倍数 22 int v=x*y;//最大值 23 int s=(int)sqrt(v);//不用重复进行寻找 24 int n=0;25 for(int i=x;i<=s;i++)26 if((v%i==0)//如果最大值能够整除当前的数，则说明找到了一组可能是真的的解 27 &&(gcd(v/i,i)==x))//如果另外一个数与当前的数的最大公约数等于输入的最大公约数 28 n++;//进行计数29 cout<<n*2;// 不进行重复的筛之后要加上另一块的 30 return 0; 31 }
方法二：分解质因数（最优）
思路：题目要求最大公约数（gcd）为3，最小公倍数（lcm）为60的两个数p、q的组数，两个数都去掉gcd后，即样例中的3、60变为1、20。这样即可变为求gcd为1，lcm为20的两个数p、q的组数，即找两个互质的数，他们的乘积为20。那么可以对20进行质因数分解，得：2、2、5。盯住其中一个数，从质因数中选择。由于两个数要求互质，所以相同的质因数要合并，得到：4、5。选法有2^2=4种：1，4，5，20。对应的四组答案即：1-20，4-5，5-4，20-1。乘以gcd得到原来题目答案：3-60，12-15，15-12，60-3。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 5 using namespace std; 6 7 int main(){ 8 int x,y,z,k=0,i;//k为不同质因数的个数 9 scanf("%d%d",&x,&y);10 if(y%x!=0) printf("%d\n",0);11 else{12 z=y/x;//除以最大公约数x13 for(i=2;i<=z;++i){//质因数分解14 if(z%i==0){15 ++k;16 while(z%i==0)z=z/i;//合并相同的质因数17 }18 }19 printf("%d\n",int(pow(2,k)));20 }21 return 0;22 }
codevs 1012 最大公约数以及最小公倍数问题 x
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。