杭电多校第三场——Fansblog（费马小定理+逆元+威尔逊定理）

题目传送门

暑假打多校的时候第一次刚遇到这题是一脸懵逼，那场比赛虽然比较惨烈，但是队友强大，还是做出了这道题，当时还给我讲了这道题，当时懵懵懂懂就知道用威尔逊定理，但是最近又做到了这道题.
emmmm…还是不会，（生气了，盘它）。

题目大意：

T组，每组一个素数P，这个数有点大（1e9到1e14）让你找到一个素数Q，Q<P,并且Q最大。也就是让你找到小于P并且距离P最近的素数。
然后求的是(Q!)mod P(即Q的阶乘取模P)。

思路：

这给Q还算好找，因为我们可以直接从P往前找，（素数相邻差别不大）判断一个数是不是素复杂度sqrt(P）。所以Q不难找。
但是Q肯定和P差不了多少。所以Q也很大。那么Q!就不能直接乘了。这时候我们就用到了威尔逊定理

（p-1）!=-1(mod p)
p为素数时候才成立。

但是我们求的是Q！mod p。那么我们可以转换一下。

Q! mod p=(P-1)!/(P-1*P-2 * P-3 *… *Q+2 *Q+1) mod P

这样我们直接求（P-1)!乘以(P-1*P-2 * P-3 *… *Q+2 *Q+1)的逆元就行了。
而且两个大数相乘可能连long long都爆了，我们用二进制进行两个大数相乘。（具体看代码）

代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
long long p;
long long mu(long long a,long long b)
{
    a%=p;
    b%=p;
    long long res=0;
    while(b)
    {

        if(b&1)
        {
            res+=a;
            res%=p;
        }
        a<<=1;
        a%=p;
        b>>=1;
    }
    return res;
}
long long ksm(long long a,long long b)
{
    long long as=1;
    a%=p;
    while(b)
    {
        if(b&1)
        {
            as=mu(as,a);
            as%=p;
        }
        a=mu(a,a);
        a%=p;
        b>>=1;
    }
    return as;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&p);
        long long q;
        q=p;

        while(1)
        {
            int flog=0;
            q--;
            for(int i=2; i<=sqrt(q); i++)
            {
                if(q%i==0)
                {
                    flog=1;
                    break;
                }
            }
            if(flog==0)
            {
                break;
            }
        }
        long long ans=1;
        for(long long i=q+1;i<=p-2;i++)
        {
            ans=mu(ans,i);
            ans%=p;
        }
        printf("%lld\n",ksm(ans,p-2)%p);
    }
    return 0;
}