2019年安徽大学ACM/ICPC实验室新生赛（公开赛）D 不定方程

题目链接：https://ac.nowcoder.com/acm/contest/2720/D

题意：对于 ax = by = c ，给出 x, y 求符合条件的 a, b, c 且 c 为最小的解，不满足条件输出 -1。

idea：容易看出 c 为x, y 的最小公倍数。设最小公倍数为 s ，所以 a = s / x，b = s / y。因为 s = x * y / __gcd(x,y) ，所以 a = y / __gcd()，b = x / __gcd()，所以 x 和 y 一定互质。若__gcd(x, y) != 1，即可输出 -1。否则为最小公倍数。

当时每想出来判断 - 1 的情况，擦

代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll t, x, y, ans;

 int main()

 {

     scanf("%lld",&t);

     while (t -- )

     {

         scanf("%lld%lld",&x,&y);

         ll s = __gcd(x, y);

         if (s != )  cout << "-1" << endl;

         else  cout << y / s << " " << x / s << " " << x * y / s << endl;

     }

     return ;

 }

巴特西

2019年安徽大学ACM/ICPC实验室新生赛（公开赛）D 不定方程

最新文章

热门文章