Fansblog

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\ast (n-1)\ast (n-2)\ast (n-3)\ast \dots \ast 3\ast 2\ast 1$. For example, $4!=4\ast 3\ast 2\ast 1=24$)

Input

First line contains an number #$T(1\le T\le 10)$ indicating the number of testcases.
Then $T$ line follows, each contains a positive prime number $P(10^9\le p\le 10^{14})$

Output

For each testcase, output an integer representing the factorial of $Q$ modulo $P$.

Sample Input

1
1000000007

Sample Output

328400734

Source

2019 Multi-University Training Contest 3

题意

• 给你一个$10^9-10^{14}$内的质数$p$，求小于$p$的最大质数的阶乘取模$p$

题解

• 威尔逊定理+$Miller\_Rabin$素数测试
• 威尔逊定理就是对于任意的正质数$k$，有
  $$((k-1)!)\%k=k-1$$
  然后对于本题先用$Miller\_Rabin$找到小于$p$的最大质数$q$，然后用威尔逊定理推一下式子：
  $$\begin{array}{rl}((p-1)!)\%p& =q!\times (q+1)\times (q+2)\times ...\times (p-1)\%p\\ & =p-1\end{array}$$
  $$\begin{array}{rl}q!& \equiv \frac{1}{(q+1)\times (q+2)\times ...\times (p-2)}(modp)\end{array}$$

代码

#include <cstdio>
#include <cstdlib>
#include <map>
using namespace std;
long long gcd(long long a,long long b) {
if (b == 0) return a;
return gcd(b,a%b);
}
long long mul(long long a,long long b,long long mod){
long long ret=0;
while(b) {
if(b & 1) ret=(ret+a)%mod;
a=(a+a)%mod;
b >>= 1;
}
return ret;
}
long long pow(long long a,long long b,long long mod) {
long long ret = 1;
while(b) {
if(b & 1) ret = mul(ret,a,mod);
a = mul(a,a,mod);
b >>= 1;
}
return ret;
}
bool check(long long a,long long n){
long long x = n - 1;
int t = 0;
while((x & 1) == 0) {
x >>= 1;
t ++;
}
x = pow(a,x,n);
long long y;
for(int i=1;i<=t;i++) {
y = mul(x,x,n);
if(y == 1 && x != 1 && x != n - 1) return true;
x = y;
}
if(y != 1) return true;
return false;
}
bool Miller_Rabin(long long n) {
if(n == 2) return true;
if(n == 1 || !(n & 1)) return false;
const int arr[12] = {2,3,5,7,11,13,17,19,23,29,31,37};
for(int i = 0; i < 12; i++) {
if (arr[i] >= n) break;
if(check(arr[i], n)) return false;
}
return true;
}
int main() {
int t;long long n;scanf("%d",&t);
while(t--) {
scanf("%lld",&n);long long p=n-1;
while(!Miller_Rabin(p)) p--;
long long ans=1;
for(long long i=p+1;i+1<n;i++) ans=mul(ans,pow(i,n-2,n),n);
printf("%lldn",ans);
}
}

最后

以上就是懦弱小刺猬为你收集整理的「hdu6608」Fansblog【Miller_Rabin+威尔逊定理】 Fansblog 的全部内容，希望文章能够帮你解决「hdu6608」Fansblog【Miller_Rabin+威尔逊定理】 Fansblog 所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。