您當(dāng)前位置：首頁 > 互聯(lián)網(wǎng) > UVA 11889-Benefit(數(shù)學(xué)_快速枚舉因子)

UVA 11889-Benefit(數(shù)學(xué)_快速枚舉因子)

來源：程序員人生發(fā)布時間：2014-11-17 08:27:30 閱讀次數(shù)：2902次

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⁷).

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

Sample Output

3
55
NO SOLUTION

題意 ：很簡單 給出a，c求滿足 lcm(a,b)==c 的最小整數(shù)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)肯定為整數(shù)，所以b肯定是c的因子，枚舉c的因子便可。

1開始純暴力枚舉c的因子T了1發(fā)，才明白數(shù)學(xué)果然是王道。 枚舉因子在判斷素數(shù)的時候就有過優(yōu)化，即只需要枚舉到sqrt(c)。 還有1個優(yōu)化條件是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
",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;
}

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈
程序員人生