結果

問題 No.187 中華風 (Hard)
ユーザー onakasuitacityonakasuitacity
提出日時 2021-03-01 20:38:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 197 ms / 3,000 ms
コード長 3,116 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 88,932 KB
最終ジャッジ日時 2024-04-14 03:48:22
合計ジャッジ時間 4,933 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 94 ms
87,348 KB
testcase_01 AC 96 ms
87,304 KB
testcase_02 AC 197 ms
88,596 KB
testcase_03 AC 183 ms
88,556 KB
testcase_04 AC 195 ms
88,932 KB
testcase_05 AC 182 ms
88,772 KB
testcase_06 AC 186 ms
88,900 KB
testcase_07 AC 186 ms
88,820 KB
testcase_08 AC 147 ms
87,900 KB
testcase_09 AC 153 ms
88,368 KB
testcase_10 AC 148 ms
87,808 KB
testcase_11 AC 181 ms
88,756 KB
testcase_12 AC 181 ms
88,528 KB
testcase_13 AC 108 ms
87,688 KB
testcase_14 AC 123 ms
88,128 KB
testcase_15 AC 106 ms
87,604 KB
testcase_16 AC 108 ms
87,448 KB
testcase_17 AC 92 ms
87,360 KB
testcase_18 AC 95 ms
87,364 KB
testcase_19 AC 92 ms
87,384 KB
testcase_20 AC 167 ms
88,692 KB
testcase_21 AC 92 ms
87,512 KB
testcase_22 AC 186 ms
88,772 KB
testcase_23 AC 95 ms
87,708 KB
testcase_24 AC 92 ms
87,444 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

from math import gcd
from collections import Counter, defaultdict

N = 1_000_000
primes = []
sieve = list(range(N + 1))
for i in range(2, N + 1):
    if sieve[i] == i:
        primes.append(i)
    for p in primes:
        if sieve[i] < p or i * p > N:
            break
        sieve[i * p] = p

def _primality_test(n):
    d = (n - 1) // ((n - 1) & -(n - 1))
    s = ((n - 1) // d).bit_length()
    for a in (2, 7, 61) if n < 4_759_123_141 else (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        y = pow(a, d, n)
        if y == 1:
            continue
        for _ in range(s):
            if y == n - 1:
                break
            y = y * y % n
        else:
            return False
    return True

def prime_factorization(n):
    res = Counter()
    queue = [n]
    for n in queue:
        if n < len(sieve):
            while n > 1:
                res[sieve[n]] += 1
                n //= sieve[n]
            continue
        if _primality_test(n):
            res[n] += 1
            continue
        c, m = 0, 1 << n.bit_length() - 3
        while True:
            c += 1
            y = g = q = r = 1
            while g == 1:
                x, k = y, 0
                for _ in range(r):
                    y = (y * y + c) % n
                while k < r and g == 1:
                    ys = y
                    for i in range(min(m, r - k)):
                        y = (y * y + c) % n
                        q = q * abs(x - y) % n
                    g = gcd(q, n)
                    k += m
                r <<= 1
            if g == n:
                g = 1
                while g == 1:
                    ys = (ys * ys + c) % n
                    g = gcd(abs(x - ys), n)
            if g != n:
                queue.append(g)
                queue.append(n // g)
                break
    return res

def modinv(a, m):
    b, u, v = m, 1, 0
    while b:
        a, b, u, v = b, a - a // b * b, v, u - a // b * v
    return u % m

def garner(R, M):
    T = []
    for r, m in zip(R, M):
        c = 1
        for t, _m in zip(T, M):
            r -= c * t
            c = c * _m  % m
        T.append(r * modinv(c, m) % m)
    return T

def crt(R, M, MOD=0):
    X = defaultdict(lambda:(0, 0))
    for r, m in zip(R, M):
        for p, e in prime_factorization(m).items():
            _e, _r = X[p]
            if (r - _r) % p**min(e, _e):
                return -1
            if e > _e:
                X[p] = (e, r)
    R, M = [], []
    for p, v in X.items():
        R.append(v[1])
        M.append(p**v[0])
    res = 0
    for t, m in zip(garner(R, M)[::-1], M[::-1]):
        res = (res * m + t) % MOD if MOD else res * m + t
    return res

def resolve():
    n = int(input())
    R, M = [0] * n, [0] * n
    for i in range(n):
        R[i], M[i] = map(int, input().split())

    if max(R) == 0:
        l = 1
        for m in M:
            l = l // gcd(l, m) * m
        print(l % MOD)
    else:
        print(crt(R, M, MOD))
resolve()
0