2019 Multi-University Training Contest 3 Fansblog

链接

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

题意

给你一个p质数，让你找小于p的最大质数q
求q!%p,p<=1e14

分析

由于数字很大你怎么找到q呢？ 所以要用到一些快速判定素数的算法
就用到Miller_Rabin 米勒罗兵算法，不会的先找博客了解一下至少知道是用来干嘛的
我就直接用别人模板了
找到q之后那么就得计算q!%p 数字很大所以不能暴力
然后就用到威尔逊定理简单来说就是如果p是素数，有个结论
(p-1)!%p=-1也就是(p-1)!%p=p-1;
因为q<p 那么 有q!(q+1)(q+2)...(p-1) % p = p-1;
你把多余的(q+1)*(q+2)...(p-1) 去掉就得到q!%p的结果了,去掉就是左乘多余数关于p的逆元,代码里有了看看
求逆元用快速幂
同时这里有个细节就是快速乘因为你快速幂的时候有可能两个数相乘超过long long ，p最大到1e14
两个数对p取余时就有可能是两个1e13相乘超过long long
当然这里可以用__int128就可以省去快速乘了，但你要重载输出输入
这里有个链接可以了解一下
[https://blog.csdn.net/HumveeA6/article/details/79806869]

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll prime[10]={2,3,5,7,11,13,19,61,2333,24251};

ll qmui(ll a,ll b,ll c)
{
    ll ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%c;
        a=(a+a)%c;
        b>>=1;
    }
    return ans;
}
ll qpow(ll a,ll b,ll c)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=qmui(ans,a,c);
        a=qmui(a,a,c);
        b>>=1;
    }
    return ans;
}
bool Miller_Rabin(ll x)
{
    ll i,j,k;
    ll s=0,t=x-1;
    if(x==2)  return 1;
    if(x<2||!(x&1))  return 0;   
    while(!(t&1))
    {
        s++;
        t>>=1;
    }
    for(i=0;i<10&&prime[i]<x;++i)
    {
        ll a=prime[i];
        ll b=qpow(a,t,x); 
        for(j=1;j<=s;++j) 
        {
            k=qmui(b,b,x); 
            if(k==1&&b!=1&&b!=x-1)
              return 0;
            b=k;
        }
        if(b!=1)  return 0;
    }
    return 1; 
}
int main()
{
    int t;
    ll p;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&p);
        ll ans=p-1;
        ll mod=p;
        while(!Miller_Rabin(p-1)){
            p--;
            ans=qmui(ans,qpow(p,mod-2,mod),mod);
        }
        printf("%lld\n",ans);
    }
    return 0;
}