AtCoder ABC186E - Throne
問題概要
解説
回目にはじめて玉座に座ることができるとすると
と立式できる。
と が互いに素でないとき
と の最大公約数を と置き、 を で割った商を 、 を で割った商を とすると
となり、 と は互いに素になる。
元の式 について考えると、整数 を用いて
のように表せられ、 は の倍数である必要があることが分かる。つまり、 が の倍数でないときは解なしとなる。 が の倍数であるとき、 を で割った商を とすると
となり、冒頭の式に帰着することが分かる。
逆元の求め方
が における の逆元であるとは
が成立することである。これは整数 を用いて
のように表せられ、 が存在すると逆元が存在するということになる。上式を満たす は拡張ユークリッドの互除法によって求めることができる。
ソースコード
#pragma GCC optimize("O3") #include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <cfloat> #include <climits> #include <ctime> #include <cassert> #include <numeric> #include <fstream> #include <functional> #include <bitset> using namespace std; using ll = long long; using P = pair<int, int>; using T = tuple<int, int, int>; template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;} template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;} constexpr int MOD = 1e9 + 7; constexpr int inf = 1e9; constexpr long long INF = 1e18; #define all(a) (a).begin(), (a).end() int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; // {g, x, y} : a x + b y = g tuple<ll, ll, ll> extgcd(ll a, ll b){ if(b == 0) return {a, 1, 0}; ll g, x, y; tie(g, x, y) = extgcd(b, a % b); return {g, y, x - a / b * y}; } int main(){ cin.tie(0); ios::sync_with_stdio(false); int t; cin>>t; while(t--){ ll n, s, k; cin>>n>>s>>k; ll g, x, y; tie(g, x, y) = extgcd(k, n); if(s % g != 0){ cout << -1 << endl; } else{ n /= g, s /= g, k /= g; ll ans = ((-s * x) % n + n) % n; cout << ans << endl; } } return 0; }