結果

問題 No.109 N! mod M
ユーザー hotpepsihotpepsi
提出日時 2014-12-22 01:28:06
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 830 bytes
コンパイル時間 558 ms
コンパイル使用メモリ 6,644 KB
実行使用メモリ 13,308 KB
最終ジャッジ日時 2023-09-02 21:22:42
合計ジャッジ時間 2,708 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
6,208 KB
testcase_01 AC 376 ms
13,308 KB
testcase_02 AC 473 ms
12,072 KB
testcase_03 AC 30 ms
6,008 KB
testcase_04 AC 37 ms
7,504 KB
testcase_05 AC 427 ms
9,416 KB
testcase_06 AC 39 ms
5,952 KB
testcase_07 WA -
testcase_08 AC 30 ms
6,040 KB
権限があれば一括ダウンロードができます

ソースコード

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