求助!!!写了个比较奇怪的办法,但是不知道为什么不对。
查看原帖
求助!!!写了个比较奇怪的办法,但是不知道为什么不对。
183881
_shy楼主2020/11/1 11:48
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
//kf,kf表示满足x=x0 + kb/d;y=y0 - ka/d中k的取值范围[kf, ks]
inline int read () // inline long long
{
	int s = 0, w = 1; char ch = getchar (); // long long s
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar ();}
	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar ();
	return s * w;
}
int t;
double tmp;
long long x, y, kf, ks;

inline int gcd (int a, int b) 
{
	if (b == 0) return a;
	if (a < b) swap (a, b);
	gcd (b, a % b);
}

inline void exgcd (int a, int b) 
{
	if (b == 0) 
	{
		x = 1, y = 0;
		return;
	}
	if (a < b) swap (a, b);
	exgcd (b, a % b);
	long long t = x;
	x = y; y = t - a / b * y;
	return;
}
int main ()
{
	//freopen (".in", "r", stdin); freopen (".out", "w", stdout);
	t = read (); 
	
	int a, b, c;
	for (int i = 1; i <= t; i++)
	{
		a = read (), b = read (), c = read ();
		int d = gcd (a, b);
		
		if (c % d != 0)
		{
			printf ("-1\n"); 
			continue;
		}
		
		exgcd (a / d, b / d);
		x = c / d * x, y = c / d * y;
		
		tmp = (0 - d) * x * 1.0 / b;
		if (tmp < 0 && tmp >= -1) kf = 0;
		else if (tmp < -1) kf = (int) (tmp + 0.00001);
		else kf = (int) tmp, kf++;
		
		tmp = y * d * 1.0 / a;
		if (tmp > 0 && tmp <= 1) ks = 0;
		else if (tmp > 1) ks = (int) (tmp - 0.00001);
		else ks = (int) tmp, ks--;
		
		if (ks < kf)
		printf ("%lld %lld\n", x + kf * b / d, y - ks * a / d);
		else
		printf ("%lld %lld %lld %lld %lld\n",
		ks - kf + 1, x + kf * b / d, 
		y - ks * a / d, x + ks * b / d,
		y - kf * a / d
		);
	}
	return 0;
}


2020/11/1 11:48
加载中...