首页 > 代码库 > UVA - 11889 Benefit

UVA - 11889 Benefit

2024-07-18 04:00:31   212人阅读

Description

Download as PDF


  Benefit 

Recently Yaghoub is playing a new trick to sell some more. When somebody gives himA Tomans, he who never has appropriate changes, asks forB 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$ \le$100000), the number of tests. Each test that comes in a separate line contains two integersA and C ( 1$ \le$A,C$ \le$107).

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
题意：已知lcm(A, B) = C ,现在知道a和c，求最小的b。思路：设A = a*b*c*d, B = a*b*c*e,那么我们可以清楚C = a*b*c*d*e，将A和C相除的话，我们就可以得到B除了gcd以外的部分了，举两个例子：A = a*b*c*d, B = a*b*c*a*b*c*e; A = a*a*a, B = a*a*a*a*b,可以得到如果我们得到的部分和A互质的话，那么这个数就是最小的了，如果不是的话不断的取gcd来补B的因子，起初以为只要一次就够了，没想到第二个样例
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a%b);
}

int main() {
	int t, A, B, C;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &A, &C);
		if (C % A) {
			printf("NO SOLUTION\n");
			continue;
		}
		B = C/A;
		int g =  gcd(A, B);
		while (g != 1) {
			B *= g;
			A /= g;
			g = gcd(A, B);
		}
		printf("%d\n", B);
	}
	return 0;
}


联系
我们