Submission #18882269

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
#define pb push_back
ll gcd (int a, int b) {
	return b ? gcd(b, a % b) : a;
}
pii extgcd(ll a, ll b) {
	if (!b) return {1, 0};
	ll k = a / b;
	pii p = extgcd(b, a - k * b);
	return {p.second, p.first - k * p.second};
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int T; cin >> T;
	while (T--) {
		ll n , s, k; cin >> n >> s >> k;
		ll g = gcd(n, k);
		if (s % g) {
			cout << "-1\n";
			continue;
		}
		pii p = extgcd(k, n);
		p.first *= -s / g, p.second *= -s / g;
		p.first %= n / g;
		if (p.first <= 0) p.first += n / g;
		cout << p.first << "\n";
	}
	return 0;
}

Submission Info

Judge Result