【HDU 6608】Fansblog（威尔逊定理+逆元+快速乘+快速幂）

阳光穿透心脏的1/2处 2021-11-10 09:14 305阅读 0赞

题目：[点击打开题目链接][Link 1]

题意：输入一个素数 P，找出 P 的前一个素数，并求出 ![Q][]! mod P的值。（1e9≤ P ≤1e14）

思路：

1.首先找出Q。因为自然数是由素数、合数、1和0组成的，并且数越大时，两个素数之间的间隔不会超过300。这里有两种方法，第一种简单粗暴，直接从P-1开始暴力枚举判断是否为素数，第二种可以将![10^\{7\}][10_7]内的素数打表出来，然后再判断是否为素数，下面提供的有两种方法，可以结合代码看看。

2.因为![Q!][Q 1] 很大，所以想办法将其化简，并且尽量与P扯上关系，虽然不晓得Q跟P到底有没有关系，但毕竟这里除了Q就是P了，说他俩没关系估计鬼都不信 ~

在[威尔逊定理][Link 2]中，当且仅当P是素数，![(P-1)!=-1(mod P)][P-1_-1_mod P] 或者 ![(P-1)!modP=P-1][P-1_modP_P-1].

由 ![Q!=1\\times 2\\times \\cdots \\times Q][Q_1_times 2_times _cdots _times Q] ， ![(P-1)!=1\\times \\cdots \\times Q\\times (Q+1) \\times(Q+2)\\times \\cdots \\times (P-1)][P-1_1_times _cdots _times Q_times _Q_1_ _times_Q_2_times _cdots _times _P-1] 得 ![Q!modP=\\frac\{(P-1)!\}\{(Q+1)\\times (Q+2)\\times \\cdots \\times (P-1)\}modP][Q_modP_frac_P-1_Q_1_times _Q_2_times _cdots _times _P-1_modP]

由威尔逊定理 ![(P-1)!modP=P-1][P-1_modP_P-1] 得 ![Q!modP=\\frac\{P-1\}\{(Q+1)\\times (Q+2)\\times \\cdots \\times (P-1)\}modP][Q_modP_frac_P-1_Q_1_times _Q_2_times _cdots _times _P-1_modP 1]

分子分母同时约掉一个（P-1）即 ![Q!modP=\\frac\{1\}\{(Q+1)\\times (Q+2)\\times \\cdots \\times (P-2)\}modP][Q_modP_frac_1_Q_1_times _Q_2_times _cdots _times _P-2_modP]

3.到这剩下的就是求分母的逆元了，在费马小定理中：

在模为素数p的情况下，有费马小定理  
a^(p-1)=1（mod p）  
那么a^(p-2)=a^-1(mod p)  
也就是说a的逆元为a^(p-2)

4.因为题中数很大，所以用快速幂、快速乘（加法代替乘法）来计算

My Code：（简单粗暴法）

#include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<algorithm>
    #include<queue>
    #include<math.h>
    #include<set>
    #include<time.h>
    #pragma GCC optimize(2)
    using namespace std;
    #define INF 1e9
    //typedef long long ll;
    typedef unsigned long long ll;
    #define PI acos(-1)
    int N = 1e7+10;
    int is_prime(ll n)///判断是否为素数
    {
        for(int i = 2; i <= N; i++)
        {
            if(n % i == 0)
                return 0;
        }
        return 1;
    }
    ll mul(ll a,ll b,ll mod)///快速乘，转换成二进制运算，类似于快速幂
    {
        ll ans = 0;
        while(b)
        {
            if(b&1)
                ans = (ans+a)%mod;
            b = b>>1;
            a = (a+a)%mod;
        }
        return ans;
    }
    ll quick_pow(ll a,ll b,ll mod)///快速幂
    {
        ll ans = 1;
        while(b)
        {
            if(b&1)
                ans = mul(ans,a,mod);
            b = b>>1;
            a = mul(a,a,mod);
        }
        return ans;
    }
    int main()
    {
        int t;
        cin >> t;
        ll p;
        while(t--)
        {
            cin >> p;
            ll q = p-1;
            while(is_prime(q) == 0)
                q--;
            ll ans = 1;
            for(ll i = q+1; i <= p-2; i++)///分母的乘积
                ans = mul(ans,i,p);
            ll res = quick_pow(ans,p-2,p);///分母的逆元
            cout << res << endl;
        }
    }

My Code：（不简单不粗暴法）

#include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<algorithm>
    #include<queue>
    #include<math.h>
    #include<set>
    #include<time.h>
    #pragma GCC optimize(2)
    using namespace std;
    #define INF 1e9
    //typedef long long ll;
    typedef unsigned long long ll;
    #define PI acos(-1)
    int N = 1e7+10;
    int prime[10000100],flag[10000100],cunt;
    int is_prime(ll n)///判断是否为素数
    {
        for(int i = 0; i < cunt && (ll)prime[i]*prime[i] < n; i++)
        {
            if(n % prime[i] == 0)
                return 0;
        }
        return 1;
    }
    void get_prime()///把10的7次方的素数进行打表
    {
        for(int i = 2;i <= N; i++)
        {
            if(!flag[i])
                prime[cunt++] = i;
            for(int j = 0; j < cunt && i*prime[j] <= N; j++)
            {
                flag[i*prime[j]] = 1;
                if(i % prime[j] == 0) break;
            }
        }
    }
    ll mul(ll a,ll b,ll mod)///快速乘，转换成二进制运算，类似于快速幂
    {
        ll ans = 0;
        while(b)
        {
            if(b&1)
                ans = (ans+a)%mod;
            b = b>>1;
            a = (a+a)%mod;
        }
        return ans;
    }
    ll quick_pow(ll a,ll b,ll mod)///快速幂
    {
        ll ans = 1;
        while(b)
        {
            if(b&1)
                ans = mul(ans,a,mod);
            b = b>>1;
            a = mul(a,a,mod);
        }
        return ans;
    }
    int main()
    {
        get_prime();
        int t;
        cin >> t;
        ll p;
        while(t--)
        {
            cin >> p;
            ll q = p-1;
            while(is_prime(q) == 0)
                q--;
            ll ans = 1;
            for(ll i = q+1; i <= p-2; i++)///分母的乘积
                ans = mul(ans,i,p);
            ll res = quick_pow(ans,p-2,p);///分母的逆元
            cout << res << endl;
        }
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6608
[Q]: https://private.codecogs.com/gif.latex?Q
[10_7]: https://private.codecogs.com/gif.latex?10%5E%7B7%7D
[Q 1]: https://private.codecogs.com/gif.latex?Q%21
[Link 2]: https://baike.baidu.com/item/%E5%A8%81%E5%B0%94%E9%80%8A%E5%AE%9A%E7%90%86/1881444?fr=aladdin
[P-1_-1_mod P]: https://private.codecogs.com/gif.latex?%28P-1%29%21%3D-1%28mod%20P%29
[P-1_modP_P-1]: https://private.codecogs.com/gif.latex?%28P-1%29%21modP%3DP-1
[Q_1_times 2_times _cdots _times Q]: https://private.codecogs.com/gif.latex?Q%21%3D1%5Ctimes%202%5Ctimes%20%5Ccdots%20%5Ctimes%20Q
[P-1_1_times _cdots _times Q_times _Q_1_ _times_Q_2_times _cdots _times _P-1]: https://private.codecogs.com/gif.latex?%28P-1%29%21%3D1%5Ctimes%20%5Ccdots%20%5Ctimes%20Q%5Ctimes%20%28Q&plus;1%29%20%5Ctimes%28Q&plus;2%29%5Ctimes%20%5Ccdots%20%5Ctimes%20%28P-1%29
[Q_modP_frac_P-1_Q_1_times _Q_2_times _cdots _times _P-1_modP]: https://private.codecogs.com/gif.latex?Q%21modP%3D%5Cfrac%7B%28P-1%29%21%7D%7B%28Q&plus;1%29%5Ctimes%20%28Q&plus;2%29%5Ctimes%20%5Ccdots%20%5Ctimes%20%28P-1%29%7DmodP
[Q_modP_frac_P-1_Q_1_times _Q_2_times _cdots _times _P-1_modP 1]: https://private.codecogs.com/gif.latex?Q%21modP%3D%5Cfrac%7BP-1%7D%7B%28Q&plus;1%29%5Ctimes%20%28Q&plus;2%29%5Ctimes%20%5Ccdots%20%5Ctimes%20%28P-1%29%7DmodP
[Q_modP_frac_1_Q_1_times _Q_2_times _cdots _times _P-2_modP]: https://private.codecogs.com/gif.latex?Q%21modP%3D%5Cfrac%7B1%7D%7B%28Q&plus;1%29%5Ctimes%20%28Q&plus;2%29%5Ctimes%20%5Ccdots%20%5Ctimes%20%28P-2%29%7DmodP