問題一覧 > 通常問題

No.109 N! mod M

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 75
作問者 : anta
4 ProblemId : 120 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:46:41

問題文

N!modMを求めよ。

入力

T
N1M1
⋮
NTMT

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

  • 1≤T≤100
  • 1≤M≤109
  • max(0,Mi−105)≤Ni≤109

出力

各テストケースi(1≤i≤T)に対し、Ni!をMiで割った余りを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!≡999999936(mod999999937)である。
  4. 1で割った余りはどんな数であれ0になる。

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