费马小定理【模板例题】

全栈程序员-站长 • 2026年3月18日下午5:49 • 未分类 • 阅读 2

费马小定理【模板例题】费马小定理如果 p 是一个质数而整数 a 不是 p 的倍数则有 a p 1 1 modp 即假如 a 是整数 p 是质数且 a p 互质即两者只有一个公约数 1 那么 a 的 p 1 次方除以 p 的余数恒等于 1 变式延伸在对质数 p 求余的条件下 n ap 1 n 1 nap 2 a 1 1 a 1 ab ab p 1 等价费马小定理参考博客例题牛牛和牛可乐的赌约题目原理 ans mod 1 1 n mod m 变式

例题

题目原理

ans = mod + 1 – ( (1/n) % mod)^m

变式可得

(1/n)%mod ==> n^mod-1/ n ==> n^mod-2

#include 
      #define ll long long const ll mod = 1e9+7; ll quick(ll base, ll power) //快速幂 { 
     long long result=1; while(power) { 
     if(power&1)//只有奇数才乘以底数 result=result*base%mod; base=base*base%mod; power=power>>1; } if(base==0){ 
     result=0; } return result%mod; } int main(){ 
     int t; scanf("%d", &t); while(t--){ 
     ll n, m, ans; scanf("%lld%lld", &n, &m); ans = quick(n, mod-2)%mod; ans = quick(ans, m); ans = mod+1-ans; printf("%lld", ans); if(t!=0) printf("\n"); } return 0; }

解题思路

实现代码

#include 
        #define ll long long using namespace std; int a[]={ 
      0}, b[]={ 
      0}; const int mod = 1e9+7; ll quick(ll base, ll power){ 
       ll ans=1; while(power){ 
       if(power&1) ans = ans*base%mod; power >>= 1; base = base*base%mod; } if(base==0) return 0; return ans; } int main(){ 
       int n; scanf("%d", &n); for(int i=0; i<n; i++) scanf("%d", &a[i]); for(int i=0; i<n; i++) scanf("%d", &b[i]); ll ans=1; for(int i=0; i<n; i++){ 
       ans = (ans*(a[i]-b[i])%mod)*quick(a[i], mod-2)%mod; } printf("%d", (mod-ans+1)%mod); return 0; }

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/213709.html原文链接：https://javaforall.net

赞 (0)

0 0

关于作者

全栈程序员-站长

133.5K 文章

3 粉丝

本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”

matlab zigzag算法,MATLAB 实现zigzag扫描（z字形扫描）

上一篇 2026年3月18日下午5:49

MultipartFile的transferTo方法

下一篇 2026年3月18日下午5:49

手把手教你整合最优雅SSM框架：SpringMVC + Spring + MyBatis

小疯手把手带你整合SpringMVC+Spring+MyBatis三大框架，俗称SSM，用它完全代替传统的SSH框架，把它们最优雅的一面发挥出来。整合配置结束后，会有一个应用实例“图书管理系统”带给大家，希望能快速上手这个框架！

全栈程序员-站长
2022年4月16日
34
idea

sublime 激活码【2021最新】

(sublime 激活码)本文适用于JetBrains家族所有ide，包括IntelliJidea，phpstorm，webstorm，pycharm，datagrip等。https://javaforall.net/100143.htmlIntelliJ2021最新激活注册码，破解教程可免费永久激活，亲测有效，上面是详细链接哦~M…

全栈程序员-站长
2022年3月21日
88
485转网口的moxa(虚拟机com口和主机com口)

影响我们一生百倍差距的四大效应观察者效应：你的世界是什么样是由你的观察决定的.这个效应是在【潜能突破】研习营课堂上发现的，我们有个练习叫三生万物，每个人都会成为一次观察者角色，当大家在成为其他角色时，他们总是发现不了自己的问题，无论我们怎样提醒都没有用，无法改变原有的模式，当他们进入观察者模式，看见其他人的行为所造成的后果时，立刻恍然大悟，主动注意自己的形为，在当下立刻发生改变.刚开始我以为这是个…

全栈程序员-站长
2022年4月17日
53
docker

Docker 常用命令！还有谁不会？[通俗易懂]

Docker 常用命令！还有谁不会？

全栈程序员-站长
2022年2月19日
42
activiti工作流开发_flowable工作流

activiti工作流开发_flowable工作流深入理解Activiti工作流Activiti作为一个流行的开源工作流引擎，正在不断发展，其6.0版本以API形式提供服务，而之前版本基本都是要求我们的应用以JDK方式与其交互，只能将其携带到我们的应用中，而API方式则可以服务器独立运行方式，能够形成一个专网内工作流引擎资源共享的方式。Activiti执行的BPMN2.0，这个规范中有几个要素见下图：其实最经常使用的是开始结束事件和任务，本文就以…

全栈程序员-站长
2022年10月6日
9
Java锁的概念「建议收藏」

Java锁的概念「建议收藏」一：悲观锁在Java中，synchronized和lock锁都是悲观锁。定义：悲观锁认为自己在使用数据的时候一定有别的线程来修改数据，因此在获取数据的时候会先加锁，确保数据不会被别的线程修改二：乐观锁定义：认为自己在使用数据时不会有别的线程修改数据，所以不会添加锁，只是在更新数据的时候去判断之前有没有别的线程更新了这个数据。如果这个数据没有被更新，当前线程将自己修改的数据成功写入。如果数据已经被其他线程更新，则根据不同的实现方式执行不同的操作（例如报错或者自动重试）。乐观锁在Java中.

全栈程序员-站长
2022年7月7日
25

发表回复

关注全栈程序员社区公众号