过了的:
num = (y + a - 1) / a;
挂了的:
num = (y - 1) / a + 1;
完整代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct ans
{
int x;
int y;
};
ans exgcd(int i, int j)
{
if(j == 0)
{
ans a;
a.x = 1;
a.y = 0;
return a;
}
ans an = exgcd(j, i % j);
int tmp = an.x;
an.x = an.y;
an.y = tmp - (i / j) * an.y;
return an;
}
int Gcd(int i, int j)
{
if(j == 0)
return i;
return Gcd(j, i % j);
}
signed main()
{
int t;
cin >> t;
for(int tt = 1; tt <= t; tt ++)
{
int a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
int g = Gcd(a, b);
if(c % g != 0)
{
printf("-1\n");
continue;
}
a /= g;
b /= g;
c /= g;
ans p = exgcd(a, b);
p.x *= c;
p.y *= c;
int ansx = (p.x % b + b) % b;
int ansy = (p.y % a + a) % a;
if(ansx == 0)
ansx = b;
if(ansy == 0)
ansy = a;
int num = 0;
int ax = ansx;
int y = (c - ax * a) / b;
num = (y + a - 1) / a;
// 就是这个地方
if(num <= 0)
printf("%lld %lld\n", ansx, ansy);
else
printf("%lld %lld %lld %lld %lld\n", num, ansx, ansy, (c - ansy * b) / a, (c - ansx * a) / b);
}
return 0;
}