求助,萌新绿绿的exgcd不知道哪里挂了 9, 10 点wa
查看原帖
求助,萌新绿绿的exgcd不知道哪里挂了 9, 10 点wa
139012
wrpwrp楼主2020/7/25 14:19
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

#define R register
#define LL long long

inline int read() {
	char a = getchar(); int x = 0,f = 1;
	for(; a>'9' ||  a<'0'; a = getchar()) if(a == '-') f = -1;
	for(;a >= '0' && a <= '9'; a = getchar()) x = x * 10 + a - '0';
	return x * f;
}

inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
inline void exgcd(LL a, LL b, LL &x, LL &y) {
	if(! b) { x = 1; y = 0; return ; }
	exgcd(b, a % b, x, y);
	int t = x; x = y; y = t - a / b * y;
}
inline void work() {
	LL a = read(), b = read(), c = read();
	LL g = gcd(a, b);
	if(c % g != 0) { printf("-1\n"); return ; }
	a /= g; b /= g; c /= g;
	LL x, y; exgcd(a, b, x, y);
	LL x0 = c * x, y0 = c * y;
	//printf("%lld %lld\n", x0, y0);
	LL le = ceil((double)-x0 / b + 1e-10); 
	LL ri = floor((double)y0 / a - 1e-10);
	//printf("%lld %lld\n", le, ri);
	if(ri < le) {
		printf("%lld %lld\n", x0 + le * b, y0 - ri * a);
	}
	else {
		printf("%lld %lld %lld %lld %lld\n", 
			ri - le + 1, x0 + le * b, y0 - ri * a, x0 + ri * b, y0 - le * a); 
	}
}

int main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int T = read();
	while(T --) work();
	return 0;	
}
2020/7/25 14:19
加载中...