HDU-6608-Fansblog(威尔逊定理+快速乘)（多校）-白红宇

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

阅读量：5009 次

发布时间：2019-06-12

本文共 1974 字，大约阅读时间需要 6 分钟。

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 )

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

Source

Recommend

chendu | We have carefully selected several similar problems for you:

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                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
                
                 <=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 y,ll mod){ ll ans=1; while(y) { if(y&1) { ans=ksc(ans,x,mod); } x=ksc(x,x,mod); y>>=1; } return ans;}bool isprime(ll x){ for(int t=0;t
                 
                  
                   >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<
                   
                    <

转载于:https://www.cnblogs.com/Staceyacm/p/11265302.html

你可能感兴趣的文章