算法
(exgcd)
这题本质是问是否存在 $x$ 满足 $s + xk \equiv 0 \pmod n$,所以需要求 $k$ 的逆元,而 $n$ 不一定是素数,所以必须用 $exgcd$ 来求。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::tuple;
using std::tie;
using ll = long long;
// {g, x, y}: ax + by = g
tuple<ll, ll, ll> exgcd(ll a, ll b) {
if (b == 0) return {a, 1, 0};
ll g, x, y;
tie(g, x, y) = exgcd(b, a % b);
return {g, y, x - a / b * y};
}
int main() {
int t;
cin >> t;
while (t--) {
ll n, s, k;
cin >> n >> s >> k;
ll g, x, y;
tie(g, x, y) = exgcd(k, n);
if (s % g != 0) {
cout << "-1\n";
continue;
}
n /= g;
s /= g;
k /= g;
ll ans = ((x * -s) % n + n) % n;
cout << ans << '\n';
}
return 0;
}