結果

問題 No.109 N! mod M
コンテスト
ユーザー なお
提出日時 2014-12-22 02:00:19
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1,120 ms / 5,000 ms
コード長 1,741 bytes
コンパイル時間 1,137 ms
コンパイル使用メモリ 161,316 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-22 04:48:45
合計ジャッジ時間 2,902 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
const int MOD = 1000000007;

const int max_r = 32000;
bool prime[max_r];

bool isprime(int n){
    if(n < max_r) return prime[n];
    if(n % 2 == 0) return false;
    for(int i = 3; i < max_r; i += 2){
        if(!prime[i]) continue;
        if(n % i == 0) return false;
    }
    return true;
}

ll extgcd(ll a,ll b,ll &m,ll &n){ll g=a;m=1;n=0;if(b)g=extgcd(b,a%b,n,m),n-=(a/b)*m;return g;}
ll divmod(ll n, ll m, ll mod){
    ll a,b;
    extgcd(m,mod,a,b);
    return (n * a) % mod;
}

ll solve(int N, int M){
    if(N >= M) return 0;    // N >= M の場合、N!の因数にMが含まれるため必ずMの倍数
    if(N == 0) return 1 % M;

    if(M < 200000){
        ll res = 1;
        for(int i = 2; i <= N; i++){
            res = (res * i) % M;
        }
        return res;
    }
    if(isprime(M)){
        // ウィルソンの定理より (M-1)! ≡ M-1 (mod M) なので、
        // N! * (N+1)(N+2)..(M-1) = (M-1)!
        // N! = M! / (N+1)(N+2)..(M-1)
        ll m = -1;
        for(int i = N+1; i < M; i++){
            m = divmod(m, i, M);
        }
        return (m+M)%M;
    }

    // M は 2e5以上の合成数
    // なんやかんやで 0 になる(´･_･`)

    return 0;
}


int T,N,M;
set<int> s;
int main(){
    memset(prime, 1, sizeof(prime));
    prime[0] = prime[1] = false;
    for(int i = 4; i < max_r; i += 2) prime[i] = false;
    for(int i = 3; i < max_r; i += 2){
        if(!prime[i]) continue;
        for(int j = i+i; j < max_r; j += i) prime[j] = false;
    }

    cin >> T;
    REP(i,T){
        cin >> N >> M;
        cout << solve(N,M) << endl;
    }
    return 0;
}
0