HDU-6608-Fansblog(威尔逊定理+快速乘)（多校）_html-js-css

概述Problem Description 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 i Problem Description 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 )

@R_404_5983@ 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 @R_404_5983@ 1 1000000007

Sample Output 328400734

Source 2019 Multi-University Training Contest 3

Recommend chendu | We have carefully selected several similar problems for you: 6613 6612 6611 6610 6609 代码：

#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<queue>#include<stack>#include<set>#include<map>#include<vector>#include<cmath>typedef long long ll;using namespace std;int prime[10000005];bool vis[10000005];int cnt =0;voID erla() {    memset(vis,false,sizeof(vis));    memset(prime,0,sizeof(prime));    for(int t=2; t<=10000003; t++) {        if(!vis[t]) {            prime[cnt++]=t;        }        for(int j=0; j<cnt&&t*prime[j]<=10000003; j++) {            vis[t*prime[j]]=true;            if(t%prime[j]==0) {                break;            }        }    }} inline ll ksc(ll x,ll y,ll mod){    return (x*y-(ll)((long double)x/mod*y)*mod+mod)%mod;     }ll ksm(ll x,ll mod){    ll ans=1;    while(y)    {        if(y&1)        {         ans=ksc(ans,x,mod);        }        x=ksc(x,mod);        y>>=1;    }    return ans;}bool isprime(ll x){    for(int t=0;t<cnt&&prime[t]<x;t++)    {                if(x%prime[t]==0)        {            return false;        }    }    return true;}int main(){    int T;    cin>>T;    erla();    while(T--)    {        ll n;        scanf("%lld",&n);        ll ans=1;        for(ll t=n-2;t>=2;t--)        {            if(isprime(t))            {                break;            }                        ans=ksc(ans,ksm(t,n-2,n),n);            //cout<<ans<<endl;        }        printf("%lld\n",ans);            }        return 0;}