AtCoder ABC 186 E - Throne (水色, 500 点)

一次合同方程式を解く問題です！

• 問題へのリンク

問題概要

円周上に 個の椅子が並べられています。そのうち 1 つは玉座です。

高橋君は最初、玉座から時計回りに数えて 個隣の椅子に座っており、次の行動を繰り返します。

• 行動：いま座っている椅子から時計回りに数えて 個隣の椅子に移動し座る

高橋君がはじめて玉座に座ることができるのは何回目の行動の後ですか？　ただし、玉座に座ることが永遠にできない場合は、代わりに -1 を出力してください。

制約

• (テストケース数)
• 
• 
• 

解法 (1)：合同方程式を立てて解く、逆元計算する

まずはオーソドックスな方法でやってみる。 回移動したときに王座に戻るとすると、それは を で割ったあまりが 0 となることを意味する。つまり

⇔

となる。よって、この一次合同方程式を解く問題へと帰着された！！　一般に を解く方法を考えよう。

と が互いに素のとき

この場合は簡潔になる。 と が互いに素なら、 となるような が存在する。このような を、 を法とした の逆元と呼ぶ。逆元は と表すことが多い

そして、 の両辺に をかけると、

となる。逆元 の求め方は次の記事などに書いた。拡張 Euclid の互除法を使うことで求められる。

qiita.com

もしくは ACL にも逆元を求める関数があるので、それが使える！

と が互いに素でないとき

一般に、整数が互いに素でない場合については、最大公約数を考えてあげることで、互いに素な場合に帰着できることが多い。今回も と の最大公約数を とおいてみることにする。そして、 を で割った商を とすると、

• 
• 

となって、 は互いに素になる。結論から書けば、次のようになる。

---

• が の倍数でないとき、解なし
• が の倍数であるとき、 として、 を解く問題へと帰着される

---

これを検証してみよう。 であるとき、 は で割り切れなければならない。よって、

を満たす整数 が存在することになる。よって

となることから、 は の倍数でなければならないことが言える。 が の倍数でないときは を満たす整数 は存在しないと結論づけられる。

逆に が の倍数であるならば、 とおくことで、

⇔
⇔

となる。これは であることを意味する。

まとめ

として、

• が の倍数でない場合は -1
• が の倍数である場合は、まず をそれぞれ で割る。これによって と は互いに素になるので、 の逆元 を求めると、 と求められる

計算量は 。以下のコードでは ACL の modint を用いた。modint を用いれば、逆元 を掛ける行為は、 で割る行為と翻訳できる。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
     
long long solve() {
    long long N, S, K;
    cin >> N >> S >> K;
    long long g = gcd(N, K);
    if (S % g) return -1;
    N /= g, S /= g, K /= g;
    modint::set_mod(N);
    modint res = -modint(S) / K;
    return res.val();
}

int main(){
    int T;
    cin >> T;
    while (T--) cout << solve() << endl;
}

解法 (2)：中国剰余定理を使う

この方法なら、 と が互いに素かどうかなども気にせず解くことができる！！

が の倍数であることを活用するのは一緒。ここで とおくと、次のように言える。

• 
• 

これらをともに満たすような整数 は中国剰余定理によって求めることができる。中国剰余定理も ACL にあるのでそれを使えば楽チン。

具体的には、解を と表したとき、 を返してくれる。しかも、もし解なしならば とした解を返してくれる。解があるかどうかの判断さえも丸投げできるのだ！！！

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
     
long long solve() {
    long long N, S, K;
    cin >> N >> S >> K;
    auto p = crt({0, N - S}, {K, N});
    if (p.second == 0) return -1;
    return p.first / K;
}

int main(){
    int T;
    cin >> T;
    while (T--) cout << solve() << endl;
}

解法 (3)：Euler の定理を活用する

実質的には解法 (1) と同じだけど、逆元計算を Euler の定理で頑張る解法。

一般に が素数であれば、 を法とした の逆元は を計算することで求められる。なぜならば Fermat の定理より

⇔

が成立するからだ。今回は mod が素数とは限らないので、この方法は使えない。代わりに Fermat の定理を拡張した Euler の定理が使える。Euler の定理とは、 と が互いに素であるとき

が成り立つというもの。ここで は Euler 関数と呼ばれる。 は 以上 以下の整数のうち と互いに素であるものの個数を表す。 を素因数分解して

としたときに

となることが知られている。Euler 関数の計算は でできる。さて、Euler の定理より

となる。よって の逆元は

と求められる。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

long long Euler(long long N) {
    long long res = N;
    for (long long p = 2; p * p <= N; ++p) {
        if (N % p == 0) {
            res = res / p * (p - 1);
            while (N % p == 0) N /= p;
        }
    }
    if (N != 1) res = res / N * (N - 1);
    return res;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
     
long long solve() {
    long long N, S, K;
    cin >> N >> S >> K;
    S = N - S;
    long long G = gcd(N, K);
    if (S % G) return -1;

    N /= G, S /= G, K /= G;
    long long phi = Euler(N);
    long long invK = modpow(K, phi-1, N);
    return S * invK % N;
}

int main(){
    int T;
    cin >> T;
    while (T--) cout << solve() << endl;
}

解法 (4)：Baby-Step Giant-Step 法を活用する

E : Baby-Step Giant-Step 解
N 回の操作で元に戻るので、答えは N 未満
Baby-Step : 0, 1, …, √N - 1 回の操作でどこにいるか
を unordered_map に持っておき、
Giant-Step : 0, √N, 2√N, … 回の操作と合わせて玉座にいけるかを調べる

— tatyam (@tatyam_prime) 2020年12月19日