問題一覧 > 通常問題

No.109 N! mod M

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 52
作問者 : antaanta
3 ProblemId : 120 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:46:41

問題文

$N! \bmod M$を求めよ。

入力

$T$
$N_1 M_1$
$\vdots$
$N_T M_T$

入力は複数のテストケースからなる。 1行目に、テストケース数を表す整数$T$が与えられる。 2行目以降、各テストケースが与えられる。

  • $1 \le T \le 100$
  • $1 \le M \le 10^9$
  • $\max(0, M_i - 10^5) \le N_i \le 10^9$

出力

各テストケース$i (1 \le i \le T)$に対し、$N_i!$を$M_i$で割った余りを1行に出力し、改行せよ。

サンプル

サンプル1
入力
4
0 2
5 100
999999936 999999937
1000000000 1
出力
1
20
999999936
0
  1. $0! = 1$
  2. $5! = 120$であり、100で余りを取った20が答えとなる。
  3. $999999936! \equiv 999999936 \pmod {999999937}$である。
  4. 1で割った余りはどんな数であれ0になる。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。