結果
| 問題 | No.187 中華風 (Hard) |
| ユーザー |
 hari64
|
| 提出日時 | 2021-05-05 19:38:39 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
AC
|
| 実行時間 | 61 ms / 3,000 ms |
| コード長 | 4,056 bytes |
| コンパイル時間 | 89 ms |
| コンパイル使用メモリ | 10,856 KB |
| 実行使用メモリ | 8,532 KB |
| 最終ジャッジ日時 | 2023-10-11 13:47:45 |
| 合計ジャッジ時間 | 2,183 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 19 ms
8,140 KB |
| testcase_01 | AC | 19 ms
8,044 KB |
| testcase_02 | AC | 33 ms
8,168 KB |
| testcase_03 | AC | 32 ms
8,224 KB |
| testcase_04 | AC | 58 ms
8,400 KB |
| testcase_05 | AC | 58 ms
8,532 KB |
| testcase_06 | AC | 57 ms
8,484 KB |
| testcase_07 | AC | 58 ms
8,484 KB |
| testcase_08 | AC | 59 ms
8,420 KB |
| testcase_09 | AC | 61 ms
8,376 KB |
| testcase_10 | AC | 60 ms
8,480 KB |
| testcase_11 | AC | 58 ms
8,428 KB |
| testcase_12 | AC | 58 ms
8,488 KB |
| testcase_13 | AC | 19 ms
8,068 KB |
| testcase_14 | AC | 19 ms
8,112 KB |
| testcase_15 | AC | 31 ms
8,060 KB |
| testcase_16 | AC | 30 ms
8,088 KB |
| testcase_17 | AC | 16 ms
8,252 KB |
| testcase_18 | AC | 18 ms
8,064 KB |
| testcase_19 | AC | 16 ms
8,284 KB |
| testcase_20 | AC | 48 ms
8,072 KB |
| testcase_21 | AC | 15 ms
8,320 KB |
| testcase_22 | AC | 57 ms
8,412 KB |
| testcase_23 | AC | 16 ms
8,316 KB |
| testcase_24 | AC | 16 ms
8,244 KB |
ソースコード
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)