为什么这两种写法看起来等价,但一个能过一个就挂了
查看原帖
为什么这两种写法看起来等价,但一个能过一个就挂了
186472
AC_loveRealNewbie楼主2023/8/14 11:58
过了的:
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;
}
2023/8/14 11:58
加载中...