HDU-6608 Fansblog 题解

题目大意

给你一个质数p，求出小于p的最大质数n，求n的阶乘模p。

解题思路

纯纯粹粹的数论题。

由威尔逊定理得，当p为质数时，$(p-2)!=1$。

所以答案为$\Large \prod_{N+1}^{p+2} inv(i)$。

质数分布密度：素数分布越来越稀疏，但1e18内任意两个质数的差不会很大，好像有个人证明了不会超过246。

参考论文：http://www.docin.com/p-775822584.html

所以直接枚举判断即可。

但是需要判断的数太大了，所以需要用Miller-Rabin素数检测算法。

不懂的戳这里。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

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 >>= 1;
	}
	return ans;
}

ll qpow(ll a, ll b, ll mod) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans = qmul(ans,a,mod);
		a = qmul(a,a,mod), b >>= 1;
	}
	return ans;
}

int check(ll num) {
	if (num == 2)	return 1;
	if (num < 2 || !(num & 1))	return 0;
	ll s, t;
	for (s = 0, t = num - 1; !(t & 1); s++, t >>= 1);
	for (int i = 1; i <= 10; i++) {
		ll a = rand() % (num - 1) + 1, k = qpow(a, t, num);
		for (int j = 1; j <= s; j++) {
			ll tmp = qmul(k, k, num);
			if (tmp == 1 && k != 1 && k != num - 1)	return 0;
			k = tmp;
		}
		if (k != 1)	return 0;
	}
	return 1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    //freopen("D:\\测试用\\in.txt", "r", stdin);
    //freopen("D:\\测试用\\out.txt", "w+", stdout);
	int t; cin >> t;
	while (t--) {
		ll num, t; cin >> num;
		t = num - 1;
		while (!check(t))	t--;
		ll ans = 1;
		for (ll i = t + 1; i <= num - 2; i++)	ans = qmul(ans,qpow(i,num-2,num),num);
		cout << ans << endl;
	}
	return 0;
}