正文

Fanblog

题意就是给你一个素数\(P\)，让你找出一个最大的且小于\(P\)的素数\(Q\)，求\(Q!\ mod\ P\)。

emmm数论题一向是弱势，这道题能做出来也是查了大佬博客上的一个结论（链接见附录），简单来说，若要求 \[ Q!\ mod\ P \] 只需要求 \[ (-1)^{Q+1}\times inv((P-1-Q)!,P) \] \(inv(a,p)\)表示的是\(a\)对\(p\)的逆元

又根据瞎猜结论，\(P\)和\(Q\)之间的距离一定不会很大，所以可以直接暴力求\(Q\)以及\((P-1-Q)!\)。套个拓展欧几里得就搞定了。

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=20005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll p,q;
ll exgcd(ll a,ll b,ll& x,ll& y)
{
    if(a==0&&b==0)  return -1;
    if(b==0){
        x=1;y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
ll inv(ll a,ll pp)
{
    ll x,y;
    ll d=exgcd(a,pp,x,y);
    if(d==1)    return (x%pp+pp)%pp;
    else    return -1;
}
bool chk(ll todo)
{
    for(ll i=2;i*i<=todo;i++){
        if(todo%i==0)   return 0;
    }
    return 1;
}
ll solve(ll todo)
{
    for(ll i=todo-1;i>=2;i--){
        if(chk(i))  return i;
    }
}
ll frac(ll todo)
{
    ll ans=1;
    for(ll i=2;i<=todo;i++)
        ans=ans%p*i%p;
    return ans;
}
int main()
{
    IOS;
    int t;cin>>t;
    while(t--){
        cin>>p;
        q=solve(p);
        ll ans=((q+1)&1?-1:1)*inv(frac(p-1-q),p);
        ans%p;
        cout<<ans<<endl;
    }
    return 0;
}

附录

• 正文所提到的结论在此处

  [威尔逊定理小讲解](https://www.cnblogs.com/Judge/p/10755703.html)

• 对于相邻两个素数的距离，最大可能为无穷大，但在题目数据范围内，这个距离不会很大。可参考以下文章：任意相邻两个素数之间的最大距离公式