题意:

给你一个1e9到1e14以内的质数p，求小于p的最大质数的阶乘取模p

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6608

题解：

队友找规律套了一个Miller_Rabin板子过了

  • Miller_Rabin素数测试是可以来测 1e18以内的大数测试法
  • 威尔逊定理就是对于任意的正质数k，有  ((k-1)!)%k = k-1

AC_code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int S = 8;
ll mult_mod(ll a,ll b,ll c) {
	a%=c;
	b%=c;
	ll ret = 0;
	ll tmp = a;
	while(b) {
		if(b&1) {
			ret += tmp;
			if(ret > c) {
				ret -= c;
			}
		}
		tmp <<= 1;
		if(tmp > c) {
			tmp -= c;

		}
		b>>=1;
	}
	return ret;
}

ll pow_mod(ll a,ll n,ll mod) {
	ll ret = 1;
	ll temp = a%mod;
	while(n) {
		if(n&1) {
			ret = mult_mod(ret,temp,mod);
		}
		temp = mult_mod(temp,temp,mod);
		n>>=1;
	}
	return ret;
}

bool check(ll a,ll n,ll x,ll t) {
	ll ret = pow_mod(a,x,n);
	ll last = ret;
	for(int i = 1 ; i <= t ; i++) {
		ret = mult_mod(ret,ret,n);
		if(ret == 1 && last != 1 &&last != n-1) {
			return true;
		}
		last = ret;
	}
	if(ret != 1) {
		return true;
	} else {
		return false;
	}
}

bool Miller_Rabin(ll n) {
	if((n&1)==0) {
		return false;
	}
	ll x = n - 1;
	ll t = 0;
	while((x&1)==0) {
		x>>=1;
		t++;
	}
	srand(time(NULL));
	for(int i = 0 ; i < S ; i++) {
		ll a = rand()%(n-1)+1;
		if(check(a,n,x,t)) {
			return false;
		}
	}
	return true;
}

int main() {
	ll t,q,p;
	cin>>t;
	while(t--) {
		cin>>p;
		q = p-1;
		while(!Miller_Rabin(q)) {
			q--;
		}
		
		ll tmp = 1;
		for(ll i = q + 1; i <= p-2; i++) {
			tmp = mult_mod(tmp, pow_mod(i, p-2 ,p), p);
		}
		cout << tmp << endl;
	}
}