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

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

前言

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

内容介绍

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

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

定理应用

那么问题来了,这个定理该怎么应用呢?

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

Sum HDU - 4704

这个题目大体的意思是说输入一个数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("%lldn", qpow(num-1));
      }
      return 0;
     }

总结

[ 2^{p-1}=1(mod p) ]

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

END

内容来源于网络如有侵权请私信删除