中国余剰定理(crt)

date: 2021-06-09 excerpt: 中国余剰定理(crt)について

中国余剰定理(crt)について

ユークリッド互除法の応用
ある数で割ったらある数のあまりが得られるとき、この対応があればもとの数字を計算することができる
使い所としては、kの倍数でシフトしてsから始まりMODで巡回しているときのkの倍数が知りたい
- <=> any % MOD == MOD - s かつ any % k == 0 のanyを知りたいと同値

コードでのイメージ

C = [3,5,7] #これで割ったら
R = [2,3,2] #この余りになる対のリスト
r,m = crt(R,C)
print(r) #23

実装

def inv_gcd(a,b):
    a=a%b
    if a==0:
        return (b,0)
    s=b;t=a
    m0=0;m1=1
    while(t):
        u=s//t
        s-=t*u
        m0-=m1*u
        s,t=t,s
        m0,m1=m1,m0
    if m0<0:
        m0+=b//s
    return (s,m0)
def inv_mod(x,m):
    assert 1<=m
    z=inv_gcd(x,m)
    assert z[0]==1
    return z[1]
def crt(r,m):
    assert len(r)==len(m)
    n=len(r)
    r0=0;m0=1
    for i in range(n):
        assert 1<=m[i]
        r1=r[i]%m[i]
        m1=m[i]
        if m0<m1:
            r0,r1=r1,r0
            m0,m1=m1,m0
        if (m0%m1==0):
            if (r0%m1!=r1):
                return (0,0)
            continue
        g,im=inv_gcd(m0,m1)
        u1=m1//g
        if ((r1-r0)%g):
            return (0,0)
        x=(r1-r0)//g % u1*im%u1
        r0+=x*m0
        m0*=u1
        if r0<0:
            r0+=m0
    return (r0,m0)

参考

math.py

例; 何回シフトしたら目的の値になるか(特定の値でMODが取られている場合)

問題

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

解答

# ライブラリは省略
T = int(input())

for t in range(T):
    N,S,K=map(int,input().split())
    # N; 最大の空間サイズ
    # S; 初期値
    # K; シフト量

    # 1. Kの倍数がNの倍数に一致するはずなので, Nx = ky <=> any % k == 0
    # 2. Nx = S + any * k <=> any'%N == N - S
    # これらから中国余剰定理より
    C = [N, K]
    R = [N-S, 0]
    r, m = crt(R, C)

    if m == 0:
        print(-1)
    else:
        print(r//K)