费马小定理（入门+内容+应用+例题）
费马小定理新手入门+总结
纵有疾风起，人生不言弃。
前言
最近新手的我做了几个和快速幂有关的题目，发现他们还经常和费马小定理联系在一起，所以有必要写一篇文章来总结一下费马小定理，以便后面更好的学习。
内容介绍
费马小定理是数论中的一个重要定理，再1636年提出。
核心：如果p是一个质数，并且整数a不是p的倍数，则有公式：$a^{p-1}\equiv1(mod p)$。
那么问题来了，这个定理该怎么应用呢？
这里举一个题目来进行说明。
这个题目大体的意思是说输入一个数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; }