杭电多校第三场——Fansblog(费马小定理+逆元+威尔逊定理)

题目传送门

暑假打多校的时候第一次刚遇到这题是一脸懵逼,那场比赛虽然比较惨烈,但是队友强大,还是做出了这道题,当时还给我讲了这道题,当时懵懵懂懂就知道用威尔逊定理,但是最近又做到了这道题.
emmmm…还是不会,(生气了,盘它)

题目大意:

T组,每组一个素数P,这个数有点大(1e9到1e14)让你找到一个素数Q,Q<P,并且Q最大。也就是让你找到小于P并且距离P最近的素数。
然后求的是(Q!)mod P(即Q的阶乘取模P)。

思路:

这给Q还算好找,因为我们可以直接从P往前找,(素数相邻差别不大)判断一个数是不是素复杂度sqrt(P)。所以Q不难找。
但是Q肯定和P差不了多少。所以Q也很大。那么Q!就不能直接乘了。这时候我们就用到了威尔逊定理

(p-1)!=-1(mod p)
p为素数时候才成立。

但是我们求的是Q!mod p。那么我们可以转换一下。

Q! mod p=(P-1)!/(P-1*P-2 * P-3 *… *Q+2 *Q+1) mod P

这样我们直接求(P-1)!乘以(P-1*P-2 * P-3 *… *Q+2 *Q+1)的逆元就行了。
而且两个大数相乘可能连long long都爆了,我们用二进制进行两个大数相乘。(具体看代码)

代码:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
long long p;
long long mu(long long a,long long b)
{
    a%=p;
    b%=p;
    long long res=0;
    while(b)
    {

        if(b&1)
        {
            res+=a;
            res%=p;
        }
        a<<=1;
        a%=p;
        b>>=1;
    }
    return res;
}
long long ksm(long long a,long long b)
{
    long long as=1;
    a%=p;
    while(b)
    {
        if(b&1)
        {
            as=mu(as,a);
            as%=p;
        }
        a=mu(a,a);
        a%=p;
        b>>=1;
    }
    return as;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&p);
        long long q;
        q=p;

        while(1)
        {
            int flog=0;
            q--;
            for(int i=2; i<=sqrt(q); i++)
            {
                if(q%i==0)
                {
                    flog=1;
                    break;
                }
            }
            if(flog==0)
            {
                break;
            }
        }
        long long ans=1;
        for(long long i=q+1;i<=p-2;i++)
        {
            ans=mu(ans,i);
            ans%=p;
        }
        printf("%lld\n",ksm(ans,p-2)%p);
    }
    return 0;
}
全部评论

相关推荐

05-09 12:23
已编辑
华南理工大学 Java
野猪不是猪🐗:给他装的,双九+有实习的能看的上这种厂我直接吃⑨✌们拿它练练面试愣是给他整出幻觉了
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:30
仁者伍敌:kpi都懒得刷了属于是
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务