当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 费马小定理（入门+内容+应用+例题）

费马小定理（入门+内容+应用+例题）

2019年07月17日  | 移动技术网IT编程  | 我要评论

僵尸漫画王小二,女客梦中惊醒,阴历生辰八字算命

费马小定理新手入门+总结

纵有疾风起，人生不言弃。

前言

最近新手的我做了几个和快速幂有关的题目，发现他们还经常和费马小定理联系在一起，所以有必要写一篇文章来总结一下费马小定理，以便后面更好的学习。

内容介绍

费马小定理是数论中的一个重要定理，再1636年提出。

​核心：如果p是一个质数，并且整数a不是p的倍数，则有公式：\(a^{p-1}\equiv1(mod\ p)\)。

定理应用

那么问题来了，这个定理该怎么应用呢？

这里举一个题目来进行说明。

这个题目大体的意思是说输入一个数n，求n被拆分成若干个正整数的结果，注意 1+2 和 2+1算作两种。n很大，需要使用数组进行存储。

输出的结果可能很大，需要mod 1e9+7，注意这个数是一个质数，正好符合费马小定理的要求。

题目解答

  1. 隔板原理+组合数求和公式

    \(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}\)

  2. 使用费马小定理

    因为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} \]

    于是计算就变得比较简单了。

  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) \]

  1. 费马小定理最重要的一点是p（模数）必须是质数，并且与a（底数）互质，只有这样才能使用。
  2. 使用这个定理的目的主要是降低计算的复杂度。
  3. 也可以用于某些数论方面的题目，这个目前自己用的比较少，不是很清楚。

end

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网