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

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

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

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

題意 ：很簡(jiǎn)單 給出a，c求滿(mǎn)足 lcm(a,b)==c 的最小整數(shù)b。沒(méi)有則輸出“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開(kāi)始純暴力枚舉c的因子T了1發(fā)，才明白數(shù)學(xué)果然是王道。 枚舉因子在判斷素?cái)?shù)的時(shí)候就有過(guò)優(yōu)化，即只需要枚舉到sqrt(c)。 還有1個(gè)優(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)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
程序員人生