题目：点击打开题目链接

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

思路：

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

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

在威尔逊定理中，当且仅当P是素数， 或者 .

 由     ，     得                                              

由威尔逊定理  得 

分子分母同时约掉一个（P-1）即  

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;
    }
}