結果

問題 No.109 N! mod M
ユーザー hotpepsi
提出日時 2014-12-22 01:12:52
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 855 bytes
コンパイル時間 519 ms
コンパイル使用メモリ 6,784 KB
実行使用メモリ 13,720 KB
最終ジャッジ日時 2024-06-12 03:38:54
合計ジャッジ時間 8,599 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 1 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

primes = [2]

def isprime(n):
  for p in primes:
    if p * p > n:
      return 1
    if (n % p) == 0:
      return 0
  return 1

def extgcd(a, b, x, y):
  d = a
  if b != 0:
    (d, x, y) = extgcd(b, a % b, y, x)
    y -= (a / b) * x
  else:
    x = 1
    y = 0
  return (d, x, y)

def modinv(a, m):
  (d, x, y) = extgcd(a, m, 1, 0)
  if d == 1:
    return (x + m) % m
  return 0

def solve(N, M):
  r = 1
  if M < N:
    return 0
  if M <= 200000:
    for n in range(2, N+1):
      r = (r * n) % M
    return r
  if not isprime(M):
    return 0
  r = M - 1
  for n in range(N+1, M):
    r = (r * modinv(n, M)) % M
  return r

n = 3
while n < 32000:
  if isprime(n):
    primes.append(n)
  n += 2

T = int(sys.stdin.readline())
for t in range(T):
  (N, M) = [int(x) for x in sys.stdin.readline().rstrip("\n").split(" ")]
  print(solve(N, M))
0