hdu6608 Fansblog(Miller_Rabin随机素数判断+威尔逊定理+费马小定理)

Farmer John keeps a website called ‘FansBlog’ .Everyday , there are many people visited this blog.One day, he find the visits has reached P , which is a prime number.He thinks it is a interesting fact.And he remembers that the visits had reached another prime number.He try to find out the largest prime number Q ( Q < P ) ,and get the answer of Q! Module P.But he is too busy to find out the answer. So he ask you for help. ( Q! is the product of all positive integers less than or equal to n: n! = n * (n-1) * (n-2) * (n-3) *… * 3 * 2 * 1 . For example, 4! = 4 * 3 * 2 * 1 = 24 )

Input

First line contains an number T(1<=T<=10) indicating the number of testcases.
Then T line follows, each contains a positive prime number P (1e9≤p≤1e14)

Output

For each testcase, output an integer representing the factorial of Q modulo P.

Sample Input

1
1000000007

Sample Output

328400734

给你一个素数p,求小于p的第一个素数q!(mod p) 

纯粹的数学题，趁此学一学 威尔逊定理 && 费马小定理 && 二次探测定理 && Miller_Rabin

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll prime[12]= {2,3,5,7,11,13,17,19,23,29,31,37};///取遍30以内的素数保证int范围内不出错，这里取到40

ll quick_multiply(ll a,ll b,ll c)///快速积  防爆long long 和快速幂差不多
{
    ll ans=0,res=a;
    while(b)
    {
        if(b&1)
            ans=(ans+res)%c;
        res=(res+res)%c;
        b>>=1;
    }
    return ans;
}

ll quick_power(ll a,ll b,ll c)///快速幂
{
    ll ans=1,res=a;
    while(b)
    {
        if(b&1)
            ans=quick_multiply(ans,res,c);
        res=quick_multiply(res,res,c);
        b>>=1;
    }
    return ans;
}

bool Mill_Rabin(ll n)///素数测试
{
    ll i,j,k;
    ll s=0,t=n-1;
    if(n==2)        ///特判
        return true;
    if(n<2||!(n&1))///特判
        return false;
    while(!(t&1))///把n分解成(2^s)*t的形式（具体见上面链接中的推导）
    {
        s++;
        t>>=1;
    }
    for(i=0; i<12&&prime[i]<n; ++i)///随机选取素数测试
    {
        ll a=prime[i];
        ll b=quick_power(a,t,n);///先算出a^t
        for(j=1; j<=s; ++j)///进行s次平方-->(a^t)^2^2^2……=a^((2^s)*t)
        {
            k=quick_multiply(b,b,n);
            if(k==1&&b!=1&&b!=(n-1))
                return false;///二次探测判断
            b=k;
        }
        if(b!=1)///费马小定理判断
            return false;
    }
    return true;
}

int main()
{
    int t;
    scanf("%d",&t);
    ll p;
    while(t--)
    {
        scanf("%lld",&p);
        ll q=n-1;
        while(!Mill_Rabin(q))///找到小于p的第一个素数
            q--;
        ll ans=1;
        for(ll i=q+1;i<p-1;i++)
            ans=quick_multiply(ans,quick_power(i,p-2,p),p);///由费马小定理推导（见下面链接）
        printf("%I64d\n",ans);
    }
    return 0;
}

详细推导