WA#13-16,求条
查看原帖
WA#13-16,求条
1235038
Ekin123楼主2024/10/3 13:05
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

long long gcd(long long a, long long b)
{
	return b == 0 ? a : gcd(b, a % b);
}

void exgcd(long long a, long long b, long long &x, long long &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return;
	}
	long long X, Y;
	exgcd(b, a % b, X, Y);
	x = Y;
	y = X - (a / b) * Y;
}

long long crt(long long a1, long long a2, long long b1, long long b2)
{
	long long x, y;
	exgcd(a1, a2, x, y);
	long long M = a1 * a2;
	long long ans = (b1 * a2 * y + b2 * a1 * x) % M;
	while (ans < 0) ans += M;
	return ans;
}

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		long long a = 399999949;
		cout << "? " << a << endl;
		long long x;
		cin >> x;
		if (x == -1ll) return 0;

		long long b = 399999959;
		cout << "? " << b << endl;
		long long y;
		cin >> y;
		if (y == -1ll) return 0;
		
		long long ans = crt(a, b, x, y);
		cout << "! " << ans << endl;
	}
	return 0;
}
2024/10/3 13:05
加载中...