首页 > 代码库 > UVA 11889-Benefit(数学_快速枚举因子)

UVA 11889-Benefit(数学_快速枚举因子)

2024-07-30 02:17:50   219人阅读


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$ \le$100000), the number of tests. Each test that comes in a separate line contains two integers A 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

题意 ：很简单 给出a，c求满足 lcm(a,b)==c 的最小整数b。没有则输出“NO SOLUTION”。
lcm(a,b)==a*b/gcd(a,b)==c --> a*b==gcd(a,b)*c; --> a/gcd(a,b)==c/b,因为a/gcd(a,b)肯定为整数，所以b肯定是c的因子，枚举c的因子即可。
一开始纯暴力枚举c的因子T了一发，才明白数学果然是王道。 枚举因子在判断素数的时候就有过优化，即只需要枚举到sqrt(c)。 还有一个优化条件是a必须是c的因子。因为
b/gcd(a,b)==c/a; 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <list>
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
ll gcd(ll a,ll b)
{
	if(b==0) return a;
	else return gcd(b,a%b);
}
void solve(ll a,ll c)
{
	// b/gcd(a,b)==c/a
	if(c%a)
	{
		puts("NO SOLUTION");
		return ;
	}
	ll b=1,ans=INF;
	int m=floor(sqrt(c)+0.5);
	while(b<=m)
	{
		if(c%b==0)
		{
			if(a*b==c*gcd(a,b))
			{
				ans=min(ans,b);
				break;
			}
			ll sb=c/b;
			if(a*sb==c*gcd(a,sb))
				ans=min(ans,sb);
		}
		b++;
	}
	if(ans!=INF)
		printf("%lld\n",ans);
	else
		puts("NO SOLUTION");
}
int main()
{
	int t;ll a,b,c;
	scanf("%d",&t);
	//   a/gcd(a,b)==c/b;
	while(t--)
	{
		scanf("%lld%lld",&a,&c);
		solve(a,c);
	}
	return 0;
}


UVA 11889-Benefit(数学_快速枚举因子)


联系
我们