結果

問題 No.109 N! mod M
ユーザー hotpepsihotpepsi
提出日時 2014-12-22 01:31:49
言語 Python2
(2.7.18)
結果
AC  
実行時間 484 ms / 5,000 ms
コード長 840 bytes
コンパイル時間 53 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 13,848 KB
最終ジャッジ日時 2024-06-22 04:48:39
合計ジャッジ時間 2,249 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
6,816 KB
testcase_01 AC 391 ms
13,848 KB
testcase_02 AC 484 ms
12,520 KB
testcase_03 AC 31 ms
6,944 KB
testcase_04 AC 38 ms
8,064 KB
testcase_05 AC 464 ms
9,912 KB
testcase_06 AC 42 ms
6,944 KB
testcase_07 AC 69 ms
12,844 KB
testcase_08 AC 32 ms
6,944 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