HDOJ6608Fansblog

题目链接

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

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为小于它的最大素数，求q！%p

  
  



• 思路
  
  显然题目可以分成两部分，1是求q，2是求q！%p。
  
  对1部分，最简单的做法就是从p-1开始向下枚举至第一个素数，对于一个足够大的素数n，不超过n的素数大约有n/ln n个即每ln n个数中大约有一个素数，故需要枚举的数量不超过100。
  
  对于2部分，直接求解最多优化到O（nlogn），加上1部分必然会超时。考虑威尔逊定理：对于素数p，有（p-1）！ 三 -1（mod p），故可以直接从（p-1）！开始推至q。
  
  -代码

  
  

#include
#define ll long long
using namespace std;
__int128 _a, _b, _m;
long long mul (long long a, long long b, long long m) {//防止爆ll
_a = a, _b = b, _m = m;
return (long long)(_a * _b % _m);
}
ll ex_gcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
else {
ll r = ex_gcd(b, a % b, y, x);
y -= x * (a / b);
return r;
}
}
ll inv(ll a, ll n) {
ll x, y;
ex_gcd(a, n, x, y);
x = (x % n + n) % n;
return x;
}
inline bool check (long long n) {
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) return true;
}
return false;
}
int main(){
ll p,q,ans;
int t;
scanf("%d",&t);
while(t--){
scanf("%I64d",&p);
ans=p-1;
q=p-1;
while(check(q)){
ans=mul(inv(q,p),ans,p);
q--;
}
printf("%I64d\n",ans);
}
}