首页 > 代码库 > UVA 11889-Benefit(数学_快速枚举因子)
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
The first line begin with an integer T ( T100000), the number of tests. Each test that comes in a separate line contains two integers A and C ( 1A, C107).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(数学_快速枚举因子)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。