なるほど・・・

けんちょんさんの記事を読みつつ自分の理解を深めるために自分でもアウトプットを勧めていきたいと思います。

けんちょんさんの記事: AtCoder ABC 186 E - Throne (水色, 500 点) - けんちょんの競プロ精進記録

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

合同方程式を立てて解く。

$x$回移動した時に玉座に戻るとすると$S + Kx \equiv 0 \pmod{N}$の式が立てられる。

つまり、$Kx \equiv -S \pmod{N}$となる。

ここで、mod の割り算は気をつける必要がある。両辺を$K$で割れば良い様に見えるが、割り算をするというのは$K*K^{-1} \equiv 1 \pmod{N}$を満たすような$K^{-1}$の値が存在する必要がある。実際に割り算をする時を両辺を$K^{-1}$で掛けことで割り算を表現する。 値$K$の逆元$K^{-1}$が存在する条件があるのでその条件を利用する。

ここで、フェルマーの小定理から、$a$と$p$が互いに素なら$a^{p-1} \equiv 1 \pmod{p} \Leftrightarrow aa^{p-2} \equiv 1 \pmod{p}$であるので、K,N が互いに素であれば、$Kx’ \equiv 1 \pmod {N}$ を満たすような$x’$は存在する。すなわち$K$の逆元$K^{-1}$は存在する。なので両辺に$K^{-1}$をかける($K$で割るのと同じ)と、$x \equiv -SK^{-1} \pmod{N}$になり解が分かる。

ここで、$K,N$が互いに素である場合について示した。

次に$K,N$が互いに素でない場合について考える。

$K,N$が互いで素でないなら$g = GCD(K,N) \neq 1$である。

ここで$K$を$g$で割った商を$K’$、$N$を$g$で割った商を$N’$とすると、

• $K = gK'$
• $N = gN'$

となり、$K’$と$N’$は互いに素になる。

ここで、元の式に戻って、$Kx + S \equiv 0 \pmod{N}$について考える。ここで、$K,N$が互いに素でないとすると、 $Kx + S \equiv 0 \pmod{N}$について$Kx + S$は$N$で割り切れる必要がある。割り切れた時の商を$m$とすると。

$$ Kx + S = Nm $$

$$ \Leftrightarrow S = Nm - Kx $$

$$ \Leftrightarrow S = gN’m - gK’x $$

$$ \Leftrightarrow S = g(N’m - K’x) $$

これにより$S$は$g$の倍数である必要がある。(すなわち、$g$の倍数でなければ解なしとなる。)ここで、$S$を$g$で割った商を$S = gS’$とする。

$$ \Leftrightarrow gS’ = g(N’m - K’x) $$

から、両辺を$g$で割ると、

$$ \Leftrightarrow S’ = N’m - K’x $$

ここから、さらに式変形すると

$$ \Leftrightarrow K’x + S’ = N’m $$

この式は合同式で表すことが出来る。

$$ \Leftrightarrow K’x + S’ \equiv 0 \pmod {N’} $$

よって、

$$ \Leftrightarrow K’x + S’ \equiv 0 \pmod {N’} $$

これは

$$ K’x \equiv -S’ \pmod {N’} $$

これにより、先程の式に帰着しました。この式では$K’,N’$が互いに素になるため、解を先程と同様に求めることが出来ます。

提出コード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <bits/stdc++.h>
#include <atcoder/all>
#define INF 1e9
#define INFLL 1ull<<60u
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

using vi = vector<int>;
using vvi = vector<vi>;
using vpii = vector<pair<int,int>>;


//min(x,y)が0以下の場合はmax(x,y)が返される
//ユークリッドの互除法を元に実装
ll gcd(ll x,ll y){
    if(x<y) swap(x,y);
    //xの方が常に大きい
    ll r;
    while(y>0){
        r=x%y;
        x=y;
        y=r;
    }
    return x;
}


void solve() {
    int T; cin >> T;


    auto solve = []() -> int {
        int N,S,K; cin >> N >> S >> K;
        auto g = gcd(N,K);
        if (S % g) return  -1;
        N/=g; S/=g; K/=g;
        atcoder::modint::set_mod(N);
        auto x = -atcoder::modint(S) / K;
        return x.val();
    };
    while(T--) cout << solve() << endl;
}


int main() {
    solve();
    return 0;
}

提出 #18933254 - パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）