本文主要是介绍uva 11889 Benefit，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题：
Recently Yaghoub is playing a new trick to sell some more. When somebody gives him A Tomans, he who never has appropriate changes, asks for B Tomans such that lowest common multiple of A and B equals to C and he will pay back a round bill. Or otherwise take some snack instead of the remaining of his money. He believes that finding such a number is hard enough that dissuades students from paying that. You should write a program that help poor students giving the appropriate amount of money to Yaghoub. Of course if there are several answers you go for students’ benefit which is the lowest of them.
Input
The first line begin with an integer T (T ≤ 100000), the number of tests. Each test that comes in a
separate line contains two integers A and C (1 ≤ A,C ≤ 10 7 ).
Output
Print the lowest integer B such that LCM(A,B) = C in a single line. If no such integer exists, print
‘NO SOLUTION’ instead. (Quotes for clarity)
Sample Input
3
2 6
32 1760
7 16
Sample Output
3
55
NO SOLUTION
中文：
就是给你两个数a和c，现在问你其中c是a和b的最小公倍数。现在问你b最小是多少？如果没有b，那么书输出NO SOLUTION。
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{if(a%b==0)return b;return gcd(b,a%b);
}
int main()
{ios::sync_with_stdio(false);int a,b,c;int t;cin>>t;while(t--){cin>>a>>c;if(a==1){cout<<c<<endl;continue;}if(c%a!=0)cout<<"NO SOLUTION"<<endl;else{b=c/a;int g=gcd(a,b);while(g!=1){a=a/g;b*=g;g=gcd(a,b);}cout<<b<<endl;}}return 0;
}
解答：
这题还有点技巧，一时没绕过来。首先可以判断，a和b的最小公倍数是c，那么c能整除a，而且c能整除b，否则就是没结果。
首先设b’=c/a，如果gcd(a,b’)==1，那么说明a和b’互质，两个互质的数的最小公倍数就是他俩的乘积，如果gcd(a,b’)!=1，那么咱设这个结果是g，由最小公倍数的公式可以得到
lcm(a,b)=a×b’/gcd(a,b’)
所以
lcm(a,b’)=a×b’/g。
这说明a和b’有最大公因子g，a和b’若是按照最小公倍数的公式去计算等价于
a×b’/g=a×(c/a)/g，结果不等于c，因为多除了一个g。现在我们要想个办法把公因子g去掉，可以让
a=a/g
让
b’=b’×g
这样做乘积的结果还是c
a/g×b’×g==a×b’
只不过公因数不会是g了，然后每次循环这个过程，直到g==1，就构造出了两个互质的数，输出b即可。
这篇关于uva 11889 Benefit的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
