ABC 186 | E - Throne

문제.

https://atcoder.jp/contests/abc186/tasks/abc186_e

해법

K마다 이동하고 N번째 X주 뒤에 도착하면 되기 때문에 아래의 연합식을 만들 수 있다.
Kx + S\equiv 0\(\bmod\N)
Kx\equiv -S\(\bmod\N)
따라서 이상은 다음과 같은 전형적인 연합방정식의 문제를 해결하는 것이다.
ax\equiv b\(\bmod\m)
이후 해설과 마찬가지로 해설을 참조할 수 있다.

코드

Tips 설치

AtCoder Librarymodint와 역원 사용 가능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;
  }
}

참고 자료

https://atcoder.jp/contests/abc186/editorial/401
https://drken1215.hatenablog.com/entry/2020/12/20/015100