HDU 6608 Fansblog——————大素数检测

冷不防 2021-11-16 07:42 179阅读 0赞

# [Fansblog][] #

点击题目查看题面 [点击这里也可以][Fansblog]

**Source**  
[2019 Multi-University Training Contest 3][]

--------------------

给你一个素数 P P P  
让给你求最接近P的素数 Q Q Q  
输出  Q ! % P Q!\\%P Q!%P

根据威尔逊定理我们可以知道  
当且仅当 P P P是素数时  
 ( P − 1 ) ! % P = − 1 (P-1)!\\%P=-1 (P−1)!%P=−1  
即  
 ( P − 1 ) ! % P = P − 1 (P-1)!\\%P=P-1 (P−1)!%P=P−1

自己打个表也能发现这个规律  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70]

我们知道了 ( P − 1 ) ! % P = P − 1 (P-1)!\\%P=P-1 (P−1)!%P=P−1  
那么 ( Q − 1 ) ! % P = ( P − 1 ) ∗ i n v ( P − 1 ) ∗ i n v ( P − 2 ) . . . ∗ i n v ( Q + 1 ) ∗ i n v ( Q ) (Q-1)!\\%P=(P-1)\*inv(P-1)\*inv(P-2)...\*inv(Q+1)\*inv(Q) (Q−1)!%P=(P−1)∗inv(P−1)∗inv(P−2)...∗inv(Q\+1)∗inv(Q)  
所以我们就可以在很快的时间里得到结果

/*--------- Hongjie ----------*/
    // #include<bits/stdc++.h>
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<map>
    #include<bitset>
    #include<set>
    #include<vector>
    #include<bits/stdc++.h>
    #define il inline
    #define ll long long
    #define RE register
    #define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
    #define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
    using namespace std;
    const int cnt=3,tab[5]={
        2,3,7,61};
    ll T,Q,P;
    ll n,m;
    ll Mul(ll x,ll y,ll mod){
        
        ll ans=(x*y-(ll)((long double)x/mod*y+0.5)*mod);
        return ans<0?ans+mod:ans;
    }
    ll Exp(ll x,ll y,ll mod){
        
        ll ans=1;
        while(y){
        
            if(y&1) ans=Mul(ans,x,mod);
            y>>=1;
            x=Mul(x,x,mod);
        }
        return ans;
    }
    bool Miller_Rabin(ll n){
        
        if(n==2||n==3||n==5||n==7||n==11||n==61) return 1;
        if(n==1||n%2==0||n%3==0||n%5==0||n%7==0||n%11==0||n%61==0) return 0;
        For(i,0,cnt) {
        
            RE ll d=n-1;
            while(!(d&1)) d>>=1;
            RE ll s=Exp(tab[i],d,n);
            while(s!=1&&s!=n-1&&d!=n-1) d<<=1,s=Mul(s,s,n);
            if(s!=n-1&&!(d&1)) return 0;
        }
        return 1;
    }
    
    ll inv(ll a,ll p) {
        
            return Exp(a,p-2,p);
    }
    
    int main(){
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
    
            scanf("%I64d",&T);
            while(T--) {
        
                    scanf("%I64d",&P);
                    for(ll q=P-1;;q--)
                            if(Miller_Rabin(q)) {
        
                                    Q = q;
                                    break;
                            }
                    ll ans = P-1;
                    for(ll i = Q+1;i<P;++i)
                            ans = Mul(ans, inv(i,P), P);
                            // ans = ans*inv(i,P)%P;
                    // cout<<ans<<endl;
                    printf("%I64d\n",ans%P);
            }
        return 0;
    }

[Fansblog]: http://acm.hdu.edu.cn/showproblem.php?pid=6608
[2019 Multi-University Training Contest 3]: http://acm.hdu.edu.cn/search.php?field=problem&key=2019%20Multi-University%20Training%20Contest%203&source=1&searchmode=source
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70]: /images/20211116/a1797ba5e4b7431099dd76b01aba42cf.png