UVA 11889 Benefit——gcd

UVA 11889 Benefit——gcd

步骤：

1若c % a != 0 , 输出no， 否则令b = c / a

2另g=gcd(a, b);

3如果g不为1，则a = a / g, b = b * g, 然后重复2直到g为1

4输出b

#include #include #include #include #include using namespace std;int gcd(int x, int y) { return (y == 0) ? x : gcd(y, x % y); }int main() { int T; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { int a, c; scanf("%d %d", &a, &c); if (c % a) { printf("NO SOLUTION\n"); continue; } int b = c / a; int g = gcd(a, b); while (g != 1) { a /= g; b *= g; g = gcd(a, b); } printf("%d\n", b); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。