费马小定理入门
2019-08-16 07:50:23来源:博客园 阅读 ()
费马小定理入门
费马小定理新手入门+总结
纵有疾风起
前言
最近新手的我做了几个和快速幂有关的题目,发现他们还经常和费马小定理联系在一起,所以有必要写一篇文章来总结一下费马小定理,以便后面更好的学习。
内容介绍
费马小定理是数论中的一个重要定理,再1636年提出。
?核心:如果p是一个质数,并且整数a不是p的倍数,则有公式:\(a^{p-1}\equiv1(mod\ p)\)。
定理应用
那么问题来了,这个定理该怎么应用呢?
这里举一个题目来进行说明。
Sum HDU - 4704
这个题目大体的意思是说输入一个数N,求N被拆分成若干个正整数的结果,注意 1+2 和 2+1算作两种。N很大,需要使用数组进行存储。
输出的结果可能很大,需要mod 1e9+7,注意这个数是一个质数,正好符合费马小定理的要求。
题目解答
隔板原理+组合数求和公式
\(1-N\)有N个元素,每个元素代表一个,分成K个数,即在\((N-1)\)个空挡里放置\((K-1)\)块隔板(最多放置N-1个挡板)。
即求组合数\(,C(0,N-1)+C(1,N-1)+...+C(N-1,N-1)\)的和,根据二项式定理,这个和为\(2^{n-1}\)
使用费马小定理
因为N很大,所以需要使用费马小定理来进行降幂
\[ 2^{n-1}mod(p)=2^{n-1-k(p-1)+k(p-1)}mod(p)=2^{n-1-k(p-1)}mod(p)*2^{k*(p-1)}mod(p) \tag{2.1} \]
又因为p是一个质数,且2和p互质,那么就可以使用费马小定理了,即
\[ 2^{k*(p-1)}mod(p)=1 \tag{2.2} \]
这样将\(公式(2.2)公式\)带入到\(公式(2.1)公式\)中得到
\[ 2^{n-1}mod(p)=2^{n-1-k(p-1)}=2^{(n-1)mod(p-1)} \tag{2.3} \]
于是计算就变得比较简单了。
快速幂进行求取\(2^{(n-1)mod(p-1)}\)的值
快速幂的复杂度为\(O(lgN)\)
代码展示
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; typedef long long ll; const ll mod=1e9+7; const ll maxn=1e8; char str[maxn]; ll qpow(ll a) //快速幂的模板 { ll ans=1, base=2; //base存储基数,这里可以调整不同的数 while(a) { if(a&1) { ans=ans*base%mod; } base=(base*base)%mod; //注意这里如果基数是2的情况下,不能使用base=(base<<1)%mod //因为这里有mod,所以写法目前是唯一的,就是代码中的写法。 a>>=1; } return ans%mod; } int main() { while(scanf("%s", str)!=EOF) { ll num=0, len=strlen(str); for(int i=0; i<len; i++) num=(num*10 + str[i]-'0') % (mod-1); //这就是对2的指数的化简,使用费马小定理 printf("%lld\n", qpow(num-1)); } return 0; }
总结
\[ 2^{p-1}=1(mod\ p) \]
- 费马小定理最重要的一点是p(模数)必须是质数,并且与a(底数)互质,只有这样才能使用。
- 使用这个定理的目的主要是降低计算的复杂度。
- 也可以用于某些数论方面的题目,这个目前自己用的比较少,不是很清楚。
END
原文链接:https://www.cnblogs.com/alking1001/p/11196510.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Window中的shellcode编写框架(入门篇) 2020-03-31
- 蓝桥杯练习(入门一) 2020-03-23
- c语言该怎么入门?C语言入门教程(非常详细) 2020-02-17
- 习题2-6:排列 2019-12-30
- 最小割最大流定理&残量网络的性质 2019-12-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash