問題一覧 > 通常問題

No.109 N! mod M

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 80
作問者 : anta
お気に入りにしたユーザー ProblemId : 120 / 自分の提出
問題文最終更新日: 2026-06-27 03:46:20
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 68 (順位表) の他の問題:

Problem Statement

Find $N! \bmod M$.

Input

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

The input consists of multiple test cases. The first line contains an integer $T$, the number of test cases. From the second line onward, the test cases are given.

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

Output

For each test case $i (1 \le i \le T)$, print the remainder when $N_i!$ is divided by $M_i$ on one line, followed by a newline.

Sample

Sample 1
Input
4
0 2
5 100
999999936 999999937
1000000000 1
Output
1
20
999999936
0
  1. $0! = 1$
  2. $5! = 120$, and taking the remainder modulo 100 gives the answer 20.
  3. $999999936! \equiv 999999936 \pmod {999999937}$.
  4. The remainder when dividing any number by 1 is 0.

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