Fansblog

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1850    Accepted Submission(s): 747

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

题目大意:找一个比P小的一个质数,求 Q!mod P 的值.

题目思路:思路就不说了,直到威尔逊定理之后就完全可以了.简要分享一下收货:

1.根据证明(记住就可以了),1e18之内的两个相邻的素数不会超过264

2.威尔逊定理:(P-1)!同余-1模 P,(P-2)!同余 P 模 1 ,所以就有 (P-2)! (mod p) = 1.所以(Q!(Q+1)!(Q+2)!(Q+3)!(Q+4)!.....(P-2)!)%p=1

所以 Q!=1/(Q+1)!(Q+2)!(Q+3)!(Q+4)!.....(P-2)!)%p,所以求一个逆元就好了.

3.如果数值太大,快速幂过程中 会爆long long ,应该在 快速幂过程中 加一个快速× 取余

附上AC代码:这个题直接 暴力 判断素数也能过:(因为他超不过264)

#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=1e9+5;
const int maxn=2e6+8;
const double eps=1e-10;
ll prime[6] = {2, 3, 5, 233, 331};
ll n,m,a,b,c;
ll qmul(ll a,ll b,ll mod)
{
    ll ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%mod;
        a=(a+a)%mod;b/=2;
    }
    return ans;
}
ll qpow(ll a,ll b,ll mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=qmul(ans,a,mod);
        b=b>>1;a=qmul(a,a,mod);
    }
    return ans;
}

bool Miller_Rabin(ll p) {
    if(p < 2) return 0;
    if(p != 2 && p % 2 == 0) return 0;
    ll s = p - 1;
    while(! (s & 1)) s >>= 1;
    for(int i = 0; i < 5; ++i) {
        if(p == prime[i]) return 1;
        ll t = s, m = qpow(prime[i], s, p);
        while(t != p - 1 && m != 1 && m != p - 1) {
            m = qmul(m, m, p);
            t <<= 1;
        }
        if(m != p - 1 && !(t & 1)) return 0;
    }
    return 1;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%lld",&n);
        ll temp=n-1;
        while(!Miller_Rabin(temp)) temp--;
        ll res=1;
        for(ll i=temp+1;i<=n-2;i++)
            res=qmul(res,i,n);
        printf("%lld\n",qpow(res,n-2,n));
    }
    return 0;
}

总结:要多去学学关于素数的定理了!