🐙

ABC 186 | E - Throne

2020/12/20に公開

競プロ

問題

解法

$K$ 個づつ移動し、 $N$ 個目にX週したあとにたどり着けばいいので以下の合同式が成り立つ。

Kx + S \equiv 0 \ (\bmod \ N)

Kx \equiv -S \ (\bmod \ N)

よって上記は以下のような典型的な合同方程式を解く問題となった。

ax \equiv b \ (\bmod \ m)

あとは解説と同じなので解説を参照するといい。

コード

実装時の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;
  }
}

ABC 186 | E - Throne

問題

解法

コード

参考

Discussion