uva 11889 Benefit（数学）

本文主要是介绍uva 11889 Benefit（数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出a,c，问是否存在一个尽可能小的数b使得lcm(a, b) == c

因为a*b/gcd(a, b) = lcm(a, b)

所以c/a = b/gcd(a, b)

而我们要求的是b，所以可以枚举b/gcd(a, b)的倍数直到c

这个过程中第一个满足条件的数就是b

代码如下：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;int gcd(int a, int b) {return b ? gcd(b, a%b) : a;
}int main(void) {int T, a, c;scanf("%d", &T);while(T--) {scanf("%d%d", &a, &c);if(c%a != 0) {puts("NO SOLUTION");} else {bool ok = false;for(int i=c/a; i<=c; i+=c/a)if(a/gcd(a, i)*i == c) {printf("%d\n", i);ok = true;break;}if(!ok) puts("NO SOLUTION");}}return 0;
}

这篇关于uva 11889 Benefit（数学）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---