結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー cologne
提出日時 2025-12-08 12:31:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 644 ms / 3,000 ms
コード長 1,298 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 381 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 77,496 KB
最終ジャッジ日時 2025-12-08 12:31:54
合計ジャッジ時間 8,581 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from functools import reduce


def input(): return sys.stdin.readline().rstrip('\n')


def factorize(n):
    ans = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            c = 0
            while n % i == 0:
                c += 1
                n //= i
            ans.append((i, c))
        i += 1
    if n != 1:
        ans.append((n, 1))
    return ans


def main():
    rems = {}

    def add_prime(q, p, c):
        if p in rems:
            aq, ac = rems[p]
            if ac > c:
                aq, q, ac, c = q, aq, c, ac
            if q % (p ** ac) != aq:
                return False

        rems[p] = (q, c)
        return True

    def add(x, y):
        f = factorize(y)
        for (p, c) in f:
            if not add_prime(x % (p ** c), p, c):
                return False
        return True

    n = int(input())
    for _ in range(n):
        x, y = map(int, input().split())
        if not add(x, y):
            return -1

    crt = [(q, p ** c) for p, (q, c) in rems.items()]
    M = reduce(lambda x, y: x * y, (b for a, b in crt), 1)
    ans = sum(q * (M // m) * pow(M // m, -1, m) for (q, m) in crt) % M

    return (M if ans == 0 else ans) % 1_000_000_007


if __name__ == '__main__':
    ret = main()
    if ret is not None:
        print(ret)
0