結果

問題 No.109 N! mod M
ユーザー hotpepsihotpepsi
提出日時 2014-12-22 01:31:49
言語 Python2
(2.7.18)
結果
AC  
実行時間 471 ms / 5,000 ms
コード長 840 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 6,692 KB
実行使用メモリ 13,520 KB
最終ジャッジ日時 2023-09-04 05:21:52
合計ジャッジ時間 2,435 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
6,032 KB
testcase_01 AC 383 ms
13,520 KB
testcase_02 AC 471 ms
11,976 KB
testcase_03 AC 30 ms
5,980 KB
testcase_04 AC 37 ms
7,480 KB
testcase_05 AC 437 ms
9,424 KB
testcase_06 AC 40 ms
6,020 KB
testcase_07 AC 67 ms
12,248 KB
testcase_08 AC 30 ms
6,056 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 or M <= 1:
    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