杭电多校Day3 1006 Fansblog

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=6608

题目大意：给你一个质数p;让你找到比p小的最大质数q，然后求出q的阶乘模p的结果。

解题思路：首先我们需要知道威尔逊定理：
对于一个质数p，p-1的阶乘模除以p等于p-1；
(p-1)! %p=（p-1）;（很nb）。
我们要求的是q的阶乘模除以p，所以我们可以得到以下式子：

q! * (q+1) * (q+2) * … *(p-3) * (p-2) * (p-1) % p = (p-1);

而我们可以把(q+1) * (q+2) * … *(p-3) * (p-2) * (p-1) % p除过去，就变成了：

q! = (p-1) * inv(p-1) * inv(p-2) * inv(p-3) * … * inv(q+2) * inv(q+1)。

inv表示逆元。解出来就是答案。

但还有一点要注意，因为p的范围在1e9到1e14，两个（p-1）相乘会爆long long，所以需要用到快速乘，（现学现用）。

大致就这些，详细看Code：

#include<iostream>

using namespace std;
typedef long long ll;
ll prime[5] = {2,5,3,233,331};
bool check(ll x){//检测是否为素数 
	if(x==1||x==0) return 0;
	if(x==2) return 1;
	for(ll i=3;i*i<x;i++){
		if(x%i==0) return 0;
	}
	return 1;
}

ll ksc(ll a,ll b,ll p){//传说中的快速乘 
	return (a*b-(ll)((long double)a/p*b)*p+p)%p;
}

ll qpow(ll a,ll b,ll p){//这个就是快速幂的至尊版，需要搭配快速乘使用 
	ll res=1;
	while(b){
		if(b&1) res=ksc(res,a,p);
		b>>=1;
		a=ksc(a,a,p);
	}
	return res;
}

bool Miller_Rabin(ll p)//这个是超级无敌秀的 米勒罗宾素数检测模板 
{                      //比上面那个素数检测快了好多倍 
    if(p < 2) return 0;//很显然我是cv过来的 
    if(p != 2 && p % 2 == 0) return 0;
    ll s = p - 1;
    while(! (s & 1)) s >>= 1;
    for(int i = 0; i < 3; ++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 = ksc(m, m, p);
            t <<= 1;
        }
        if(m != p - 1 && !(t & 1)) return 0;
    }
    return 1;
}

ll inv(ll x,ll p){//求解一个数的逆元 
	return qpow(x,p-2,p);
}

int main(){
	int t;
	cin>>t;
	while(t--){
		ll p,ans;
		cin>>p;
		ans=p-1;
		for(ll x=p-2;x>=1;x-=2){
			if(Miller_Rabin(x)){//这里也可以换成check（x）检测 
				for(ll j=x+1;j<p;j++){
					ans=ksc(ans,inv(j,p),p);
				}
				cout<<ans<<endl;
				break;
			}
		}
	}
	
	return 0;
}