yukicoder 0109 N! mod M
問題文概要
$N! \mod M$ を求めよ.
制約
$\max(0, M - 10^5) \le N \le 10^9$
コーナーケース
$N = 0, M = 1$.
解法
$N, M$ が小さい時は愚直に計算.
$M$ が十分に大きく, 素数でない時, $p^e \divides M$ なら $p^e \le M/2 \le N$ になる. 従って, 各 $p^e$ で $N! \equiv 0 \pmod p^e$ となるから, $N \equiv 0 \pmod M$.
一方, $M$ が素数の時は Wilson の定理 $(p-1)! \equiv -1 \pmod p$ を使って, 後ろから計算すればよい.
ソースコード
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool solve(){
int T;
cin >> T;
rep(_, T){
ll n, m;
cin >> n >> m;
if(n >= m or m == 1){ cout << 0 << endl; continue; }
if(n < 1000 * 1000){
ll res = 1;
rep(i, n+1) if(i) (res *= i) %= m;
cout << res << endl;
continue;
}
if(!is_prime(m)){ cout << 0 << endl; continue; }
ll res = 1;
for(int i = n+1; i <= m-1; ++i) (res *= i) %= m;
res = powMod(res, m-2, m);
(res *= m-1) %= m;
if(res < 0) res += m;
cout << res << endl;
}
return true;
}