No.109 N! mod M
レベル :
/ AI推定難易度 : 1600
/ 実行時間制限 : 1ケース 5.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 :
anta
タグ : / 解いたユーザー数 80
作問者 :
anta
問題文最終更新日: 2026-06-27 03:46:20
English (AI translation)
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
- $0! = 1$
- $5! = 120$, and taking the remainder modulo 100 gives the answer 20.
- $999999936! \equiv 999999936 \pmod {999999937}$.
- The remainder when dividing any number by 1 is 0.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。