結果

問題 No.187 中華風 (Hard)
ユーザー hari64hari64
提出日時 2021-05-05 19:38:39
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 76 ms / 3,000 ms
コード長 4,056 bytes
コンパイル時間 101 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-09-13 12:30:37
合計ジャッジ時間 2,274 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
10,880 KB
testcase_01 AC 35 ms
10,880 KB
testcase_02 AC 48 ms
10,880 KB
testcase_03 AC 46 ms
10,880 KB
testcase_04 AC 73 ms
11,008 KB
testcase_05 AC 72 ms
11,008 KB
testcase_06 AC 73 ms
11,008 KB
testcase_07 AC 72 ms
11,136 KB
testcase_08 AC 76 ms
11,008 KB
testcase_09 AC 75 ms
11,008 KB
testcase_10 AC 74 ms
11,136 KB
testcase_11 AC 72 ms
11,136 KB
testcase_12 AC 73 ms
11,008 KB
testcase_13 AC 34 ms
10,880 KB
testcase_14 AC 33 ms
10,880 KB
testcase_15 AC 46 ms
10,880 KB
testcase_16 AC 46 ms
10,880 KB
testcase_17 AC 30 ms
10,880 KB
testcase_18 AC 33 ms
10,880 KB
testcase_19 AC 30 ms
10,880 KB
testcase_20 AC 63 ms
11,136 KB
testcase_21 AC 29 ms
11,008 KB
testcase_22 AC 72 ms
11,008 KB
testcase_23 AC 30 ms
10,880 KB
testcase_24 AC 30 ms
10,880 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def _inv_gcd(a, b) -> (int, int):
    """
    返り値は(gcd(a,b),x) (ただしxa≡g (mod b) 0<=x<b//g)
    https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp
    """
    assert 0 <= a and 1 <= b
    a %= b
    if a == 0:
        return (b, 0)
    s = b  # m0*a≡s (mod b) これらの性質をm0,m1は満たしていることに注意
    t = a  # m1*a≡t (mod b)
    m0 = 0  # s*|m1|+t*|m0|<=b
    m1 = 1  # また、a<bよりt<sが成立
    while t:
        # この三行は互除法そのもの
        u = s // t
        s -= t * u
        s, t = t, s
        # m0とm1が先ほど挙げた性質を保持し続ける様に変更する oがoldm、nがnewを示すとして
        # o_m0*a=o_s o_m1*a=o_t (冒頭にあげた性質)
        # n_s=o_t n_t=o_s-o_t*u (互除法による変更)
        # o_m1*a=n_s (o_m0-o_m1*u)*a=n_t (代入して整理)
        # これを先の性質の式と見比べるとn_m0=o_m1 n_m1=o_m0-o_m1*uを得る これが下の式の正体
        # 三つ目の性質も保たれていることは代入すればすぐわかる
        m0 -= m1 * u
        m0, m1 = m1, m0
    if m0 < 0:  # 三つ目の性質を利用すると|m0|<=b//s=b//g この辺りの証明が、ACLのコメントは少し分かりにくい
        m0 += b // s
    return (s, m0)


def crt(rs: list, mods: list) -> (int, int):
    """
    同じ長さのリストr,mを引数に取り、このリストの長さをnとした時
    x≡rs[i] (mod ms[i]) ∀i∊{0,1,…,n-1}を解く 
    答えが存在するならばx≡y(mod z) (0<=y<z=lcm(ms))なる(y,z)を返す
    制約 len(rs)=len(ms) 1<=ms[i] 法が互いに素である必要はない
    計算量 O(nlog(lcm(ms)))
    簡単に言えば中国剰余定理 (Chinese Remainder Theorem)のことである
    https://qiita.com/drken/items/ae02240cd1f8edfc86fd
    https://manabitimes.jp/math/837
    https://manabitimes.jp/math/838
    中国剰余定理は言い換えれば一次不定方程式(ベズー等式)を繰り返し解くことに他ならない
    ax+by=cが整数解を持つ必要十分条件がcがgcd(a,b)の倍数であることなどを
    思い出しておくと分かりやすいだろう
    https://manabitimes.jp/math/674
    """
    assert len(rs) == len(mods)
    n = len(rs)
    r0 = 0  # 0<=r0<m0という条件の下で考えていく
    m0 = 1  # x≡0 (mod 1)は恒等式 これにより最初のステップを例外扱いしないで済む
    for i in range(n):  # x≡r0(mod m0)≡r1(mod m1)という連立式を繰り返し解く
        assert 1 <= mods[i]
        r1 = rs[i] % mods[i]
        m1 = mods[i]
        if m0 < m1:  # m1<=m0にする
            r0, r1 = r1, r0
            m0, m1 = m1, m0
        if m0 % m1 == 0:
            if r0 % m1 != r1:  # 大小関係より矛盾
                return (0, 0)
            else:  # 新しい式の主張は既に満たされている
                continue
        # 以上の処理でm1<m0,2*max(m0,m1)<=lcm(m0,m1)が保証される
        # 解をx≡r2 (mod lcm(m0,m1))と置くと
        # r2≡r0 (mod m0) r2≡r1 (mod m1) より (r0+x*m0)≡r1 (mod m1)
        # つまり x*m0≡r1-r0 (mod m1) これを法も含めてg(=gcd(m0,m1))で割ると
        # x≡((r1-r0)*(u0^-1))/g (mod u1)  (m0/g=u0 m1/g=u1)
        # この辺りは少しACLと説明を変えている そちらもそちらで分かりやすい
        g, im = _inv_gcd(m0, m1)  # im=(u0)^-1 (mod u1) (0<=im<u1)
        u1 = m1 // g
        if (r1 - r0) % g:  # 互いにその場合に帰着できないならそれは解けない
            return (0, 0)
        x = (r1 - r0) // g * im % u1  # 先述の式
        r0 += x * m0  # ≡r2 (mod m2)
        m0 *= u1  # =m2(=lcm(m0,m1))
        if r0 < 0:
            r0 += m0
    return (r0, m0)

  
n=int(input())
rs=[]
mods=[]
for i in range(n):
    r,mod=map(int,input().split())
    rs.append(r)
    mods.append(mod)
MOD=10**9+7
ans=crt(rs=rs,mods=mods)
print((ans[0] if ans[0]!=0 else ans[1])%MOD if ans!=(0,0) else -1)
0