快速幂模闆及應用

實作原理：

a^b mod c = （（a^2）^b/2）mod c，b為偶數，

a^b mod c = （（a^2）^b/2 * a）mod c，b為奇數。

代碼：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<ctime>
using namespace std;
typedef unsigned long long ll;
ll a,b,MOD;

ll powr(ll a,ll i)//位運算遞歸版 
{
  if (i==) return ;
  int temp=powr(a,i>>);
  temp=temp*temp%MOD;
  if (i&) temp=(ll)temp*a%MOD;
  return temp%MOD;
}

ll f(ll a,ll b,ll n)//位運算非遞歸 
{
  int t,y;
  t=; y=a;
  while (b!=)
  {
      if (b&==) t=t*y%MOD;
      y=y*y%MOD; b=b>>;
  }
  return t;
}

int pow1(int a,int b)//正常求幂 
{
   int r=;
   while(b--) r*=a;
   return r;
}

int pow2(int a,int b)//一般快速求幂 
{
    int r=,base=a;
    while(b!=)
    {
        if(b%) r*=base;
        base*=base;
        b/=;
    }
    return r;
}

int main()
{
    scanf("%llu%llu%llu",&a,&b,&MOD);
    printf("%d\n",powr(a,b));
    printf("Time used = %0.3f\n",(double)clock()/CLOCKS_PER_SEC); 
    return ;
}
           

應用：

費馬小定理求逆元的實作。

費馬小定理：假如p是質數，且gcd(a,p)=1，那麼 a^(p-1)≡1（mod p）。

即：假如a是整數，p是質數，且a,p互質(即兩者隻有一個公約數1)，那麼a的(p-1)次方除以p的餘數恒等于1。a^(p-1)%p = 1

逆元：如果a*x≡1（mod p），則稱x為a關于mod p意義下的逆元（inv），x即是1/a。

那麼我們就可以将x換為a^(p-2)，逆元定義式便轉化為了費馬小定理公式，那麼a關于mod p意義下的逆元即為a^(p-2)——快速幂求解。