首页 > 代码库 > UVa 11889 最小公倍数
UVa 11889 最小公倍数
https://vjudge.net/problem/UVA-11889
题意：
输入两个整数A和C，求最小的整数B使得lcm（A,B）=C。
思路：
首先C是A的公倍数，如果C%A不为0肯定是无解的。
接下来先让B=C/A，求g=gcd（A,B），如果g不为1的话，那么A、B的最小公倍数就是A*B/g，不等于c。
所以我们要去掉这个g，也就是让A/g，B*g。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 using namespace std; 6 7 int A,C; 8 9 int gcd(int a,int b)10 {11 return b==0?a:gcd(b,a%b);12 }13 14 int main()15 {16 int T;17 scanf("%d",&T);18 while(T--)19 {20 scanf("%d%d",&A,&C);21 if(C%A)22 {23 printf("NO SOLUTION\n");24 continue;25 }26 int B=C/A;27 int g=gcd(A,B);28 int t=1;29 while(g!=1)30 {31 t*=g;32 A/=g;33 g=gcd(A,B);34 }35 printf("%d\n",B*t);36 }37 return 0;38 }
UVa 11889 最小公倍数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。