0

n!modulo p を計算するために次のコードを書きました... n と p が近いと仮定すると...しかし、かなり面白い方法で実行されているため、バグを理解できません..どこかにオーバーフローがあります..制約は1 < P <= 2*10^9

1 <= N <= 2*10^9 ですが、いくつかのケースでは問題なく動作します...エラーの可能性があります。私は使用しました

(a/b)mod p = ((a mod p)*(b^(p-2))mod p)mod p

p素数です....そしてウィルソンの定理(p-1)! mod p = p-1

#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
unsigned int pow(unsigned int a, unsigned n,unsigned int p) {
unsigned int ret = 1;
while(n) {
if((n&1)== 1) ret=(ret*a)%p;
a=a%p;
a=(a*a)%p;
 n=n>>1;
}
return ret;
}
int main(){_
int t;
cin>>t;
while(t--){
    unsigned int n,p;
    long long int r;
    cin>>n>>p;
    r=p-1;
    if(n>=p){
        cout<<"0\n";
    }
    else{
        for(unsigned int i=p-1;i>n;i--){
            r=((long long)r*pow(i,p-2,p))%p;

        }
        cout<<r<<"\n";
    }
}   
return 0;
}
4

1 に答える 1

1

21！は 51090942171709440000 ですが、2^64 は 1844674407370955161 しかありません。したがって、unsigned long longが 64 ビットの量である場合 (可能性が高いため)、適合しません。

于 2013-11-02T15:23:06.517 に答える