AtCoder Beginner Contest 186 (パナソニックプログラミングコンテスト) E-Throne

AtCoder Beginner Contest 186 (パナソニックプログラミングコンテスト) (ABC-186) E - Throne についての記事です．

問題へのリンク

atcoder.jp

ABC-186 E Throne

解法

全体で必要なステップ数は，

• Kの倍数であって (つまり，mod K で 0 である)
• mod N で -S である

だから，中国剰余定理で求められる．これを K で割れば答になる．

感想

コンテスト中は，拡張互除法の結果を一生懸命場合分けしていました． 中国剰余定理ってこういうふうに使うんですね．

コード

#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;
#include <atcoder/math>
using namespace atcoder;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  auto solve = [&]() -> ll {
    ll N, S, K; cin >> N >> S >> K;
    auto [y, z] = crt(vector<ll>({0, -S}), vector<ll>({K, N}));
    if (y == 0 && z == 0) return -1;
    return y / K;
  };

  ll T; cin >> T;
  for (ll t = 0; t < T; t++) cout << solve() << "\n";

  return 0;
}