結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー onakasuitacity
提出日時 2021-02-28 19:16:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 92 ms / 2,000 ms
コード長 3,124 bytes
コンパイル時間 337 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 87,524 KB
最終ジャッジ日時 2024-10-02 21:53:17
合計ジャッジ時間 3,612 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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():
    B, M = [0] * 3, [0] * 3
    for i in range(3):
        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
    else:
        ans = 0
        for t, m in zip(T[::-1], M[::-1]):
            ans = ans * m + t
    print(ans)
resolve()
0