結果

問題 No.187 中華風 (Hard)
ユーザー onakasuitacityonakasuitacity
提出日時 2021-02-28 18:56:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 178 ms / 3,000 ms
コード長 3,263 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 82,424 KB
実行使用メモリ 89,008 KB
最終ジャッジ日時 2024-04-12 10:11:36
合計ジャッジ時間 4,144 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
87,520 KB
testcase_01 AC 78 ms
87,388 KB
testcase_02 AC 173 ms
88,776 KB
testcase_03 AC 165 ms
88,596 KB
testcase_04 AC 163 ms
88,668 KB
testcase_05 AC 154 ms
88,452 KB
testcase_06 AC 158 ms
88,528 KB
testcase_07 AC 150 ms
88,628 KB
testcase_08 AC 114 ms
87,824 KB
testcase_09 AC 117 ms
87,676 KB
testcase_10 AC 114 ms
87,620 KB
testcase_11 AC 156 ms
88,804 KB
testcase_12 AC 164 ms
88,640 KB
testcase_13 AC 101 ms
87,768 KB
testcase_14 AC 114 ms
87,872 KB
testcase_15 AC 178 ms
88,760 KB
testcase_16 AC 172 ms
89,008 KB
testcase_17 AC 78 ms
87,352 KB
testcase_18 AC 81 ms
87,440 KB
testcase_19 AC 80 ms
87,496 KB
testcase_20 AC 141 ms
88,264 KB
testcase_21 AC 77 ms
87,252 KB
testcase_22 AC 155 ms
88,696 KB
testcase_23 AC 78 ms
87,300 KB
testcase_24 AC 78 ms
87,228 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

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

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 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(B, M):
    T = []
    for b, m in zip(B, M):
        x, c = 0, 1
        for t, _m in zip(T[::-1], M[len(T)-1::-1]):
            x = (x * _m + t) % m
            c = c * _m  % m
        T.append((b - x) * modinv(c, m) % m)
    return T

def crt(B, M):
    X = {} # p -> (e, b) s.t. x = b mod p^e
    for b, m in zip(B, M):
        for p, e in prime_factorization(m).items():
            if p in X:
                _e, _b = X[p]
                if (b - _b) % (p ** min(e, _e)):
                    return [], []
                if e > _e:
                    X[p] = (e, b)
            else:
                X[p] = (e, b)
    B, M = [], []
    for p, v in X.items():
        e, b = v
        B.append(b)
        M.append(p ** e)
    return garner(B, M), M

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

    T, M = crt(B, M)
    if not T:
        ans = -1
    elif max(T) == 0:
        ans = 1
        for m in M:
            ans = ans * m % MOD
    else:
        ans = 0
        for t, m in zip(T[::-1], M[::-1]):
            ans = (ans * m + t) % MOD
    print(ans)
resolve()
0