🐙
ABC 186 | E - Throne
問題
解法
よって上記は以下のような典型的な合同方程式を解く問題となった。
あとは解説と同じなので解説を参照するといい。
コード
実装時のTips
- AtCoder Libraryの
modintと、逆元はinvを使えばいい
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;
// ax ≡ b (mod m)を解く
ll solve(ll a, ll b, ll m) {
ll d = gcd(gcd(a, b), m);
a /= d;
b /= d;
m /= d;
ll g = gcd(a, m);
if (b % g != 0) return -1;
modint::set_mod(m);
modint res = modint(b) * modint(a).inv();
return res.val();
}
int main() {
ll t;
cin >> t;
for (int i = 0; i < t; i++) {
ll n, s, k;
cin >> n >> s >> k;
auto v = solve(k, -s, n);
cout << v << endl;
}
}
参考
Discussion