精选文章 Fansblog HDU - 6608

Fansblog HDU - 6608

作者:Chter0 时间: 2019-11-11 01:51:19
Chter0 2019-11-11 01:51:19

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前面的第一个素数m与p的间隔大概在log p,m较大不能直接求m!,但我们可以通过威尔逊定理求得(p-1)!再除以m+1到p-1之间的数求得m!。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1e7+10;
const double exc=1e-7;
long long mod;
int cnt;
bool vis[maxn+10];
long long prime[maxn+10];
void getprime()
{
    for(int i=2; i<=maxn; i++)
    {
        if(!vis[i])
            prime[cnt++]=i;
        for(int j=0; j<=maxn;>>=1;
    }
    return ans%mod;
}
long long fastpow(long long a,long long b)
{
    long long ans=1;
    while(b)
    {
        if(b&1)
            ans=fastmul(ans,a);
        a=fastmul(a,a);
        b>>=1;
    }
    return ans;
}
int main()
{
    int t;
    getprime();
    scanf("%d",&t);
    while(t--)
    {
        long long p,m;
        scanf("%lld",&p);
        mod=p;
        m=p-1;
        while(!isprime(m)) m--; 
        long long ans=p-1;
        for(long long i=p-1; i>=m+1; i--)
            ans=fastmul(ans,fastpow(i,p-2));
        printf("%lld\n",ans);
    }
    return 0;
}
<=maxn;>

 

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:golang 枚举 iota

下一篇:冒泡排序的两种方法

您可能感兴趣

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。