結果

問題 No.187 中華風 (Hard)
ユーザー onakasuitacityonakasuitacity
提出日時 2021-02-28 19:05:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 209 ms / 3,000 ms
コード長 3,159 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 88,960 KB
最終ジャッジ日時 2024-10-02 21:52:41
合計ジャッジ時間 4,931 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 101 ms
87,236 KB
testcase_01 AC 109 ms
87,680 KB
testcase_02 AC 196 ms
88,960 KB
testcase_03 AC 206 ms
88,832 KB
testcase_04 AC 185 ms
88,848 KB
testcase_05 AC 202 ms
88,832 KB
testcase_06 AC 201 ms
88,576 KB
testcase_07 AC 187 ms
88,576 KB
testcase_08 AC 142 ms
87,848 KB
testcase_09 AC 145 ms
87,752 KB
testcase_10 AC 140 ms
87,824 KB
testcase_11 AC 188 ms
88,832 KB
testcase_12 AC 186 ms
88,704 KB
testcase_13 AC 109 ms
87,552 KB
testcase_14 AC 125 ms
88,064 KB
testcase_15 AC 202 ms
88,816 KB
testcase_16 AC 209 ms
88,704 KB
testcase_17 AC 112 ms
87,424 KB
testcase_18 AC 114 ms
87,168 KB
testcase_19 AC 110 ms
87,296 KB
testcase_20 AC 189 ms
88,320 KB
testcase_21 AC 110 ms
87,424 KB
testcase_22 AC 208 ms
88,704 KB
testcase_23 AC 109 ms
87,296 KB
testcase_24 AC 108 ms
87,296 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(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 = defaultdict(lambda:(0, 0))
    for b, m in zip(B, M):
        for p, e in prime_factorization(m).items():
            _e, _b = X[p]
            if (b - _b) % p**min(e, _e):
                return [], []
            if e > _e:
                X[p] = (e, b)
    B, M = [], []
    for p, v in X.items():
        B.append(v[1])
        M.append(p**v[0])
    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