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

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 

T100000

1A, C10⁷

Output 

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的因子便可。

1开始纯暴力枚举c的因子T了1发，才明白数学果然是王道。 枚举因子在判断素数的时候就有过优化，即只需要枚举到sqrt(c)。 还有1个优化条件是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;
}

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠