結果

問題 No.109 N! mod M
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:47:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 170 ms / 5,000 ms
コード長 1,846 bytes
コンパイル時間 143 ms
コンパイル使用メモリ 82,212 KB
実行使用メモリ 61,212 KB
最終ジャッジ日時 2025-03-20 20:47:43
合計ジャッジ時間 1,276 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import math

def factorize(m):
    factors = {}
    while m % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        m //=2
    i =3
    max_i = int(math.sqrt(m)) +1
    while i <= max_i and m !=1:
        while m %i ==0:
            factors[i] = factors.get(i, 0) +1
            m //=i
            max_i = int(math.sqrt(m)) +1
        i +=2
    if m !=1:
        factors[m] =1
    return factors

def legendre(n, p):
    total =0
    while n>0:
        n =n//p
        total +=n
    return total

def is_prime(m):
    if m <2:
        return False
    if m ==2:
        return True
    if m %2 ==0:
        return False
    for i in range(3, int(math.sqrt(m)) +1, 2):
        if m%i ==0:
            return False
    return True

def solve():
    input = sys.stdin.read().split()
    idx=0
    T = int(input[idx])
    idx +=1
    for _ in range(T):
        N = int(input[idx])
        M = int(input[idx+1])
        idx +=2
        if M ==1:
            print(0)
            continue
        factors = factorize(M)
        can_divide =True
        for p, k in factors.items():
            lp = legendre(N, p)
            if lp <k:
                can_divide = False
                break
        if can_divide:
            print(0)
            continue
        # step4: compute N! mod M
        if is_prime(M):
            if N == M-1:
                print(M-1)
            else:
                product =1
                for i in range(N+1, M):
                    product = (product * i) % M
                inv = pow(product, M-2, M)
                res = ((M-1) * inv) % M
                print(res)
        else:
            res =1
            for i in range(2, N+1):
                res = (res * i) % M
                if res ==0:
                    break
            print(res % M)

if __name__ == "__main__":
    solve()
0