結果
問題 | No.109 N! mod M |
ユーザー |
|
提出日時 | 2014-12-21 23:27:20 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 102 ms / 5,000 ms |
コード長 | 994 bytes |
コンパイル時間 | 402 ms |
コンパイル使用メモリ | 55,960 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-22 04:47:02 |
合計ジャッジ時間 | 1,153 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 9 |
ソースコード
#include <iostream> using namespace std; typedef long long ll; const int B = 200000; ll mod_pow(ll x, ll e, ll MOD){ ll v = 1; for(;e;e>>=1){ if(e & 1){ v = (v * x) % MOD; } x = (x * x) % MOD; } return v; } bool is_prime(ll n){ for(ll d=2;d*d<=n;d++)if(n % d == 0)return false; return true; } ll solve(ll N, ll M){ if(M == 1)return 0; if(N >= M)return 0; if(is_prime(M)){ ll sp = 1; for(ll k=N+1;k<M;k++)sp = (sp * k) % M; ll res = mod_pow(sp, M - 2, M); res = (M - res) % M; return res; } else { if(M <= B){ ll res = 1; for(ll i=1;i<=N;i++)res = (res * i) % M; return res; } else { return 0; } } } int main(){ int T; cin >> T; for(int i=0;i<T;i++){ ll N, M; cin >> N >> M; cout << solve(N, M) << endl; } return 0; }