結果

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

ソースコード

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, y, x) = 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)
  return (x + m) % m

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 * n) % M
  return modinv(r, M)

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