数论基础知识1----快速幂

1.1 模运算
定义取模运算为a除以m的余数,记为:

      a mod m = a % m;

取模结果
0<=a mod m<=m-1;
取模操作性质:
加:(a+b) mod m =( a mod m + b mod m) mod m;
减:(a-b) mod m =( a mod m - b mod m) mod m;
乘:(ab) mod m =( a mod m b mod m) mod m;
以上方法对于除法不适用

1.2 快速幂
1.2.1 分治法

int fastPow(int a,int n){//分治法
if(n==1)return a;
int temp=fastPow(a,n/2);
if(n%2==0)
return temp*temp;//偶数个a;
else
return temptempa; //奇数个a;
}

1.2.2 按位乘
将所需求的指数化为二进制按位进行累乘
(1)n&1,取n的最后一位，判断需不需要进行累乘
(2)n>>=1,将n右移一位，目的把刚处理的最后一位去除掉。
例如 a的11次方 为 a的8次方，a的2次方，a的1次方相乘
对应二进制位 1011;
int fastPow2(int a,int n){ //按位乘

int temp=1,base=a;
while(n){
    if(n&1)
    temp*=base;
    base*=base;
    n>>=1;
    
}
return temp;

}

快速幂取模
const int mod=200907;
int fastPow3(int a,int n){

int temp=1,base=a;
while(n){
    if(n&1)
    temp=(temp*base)%mod;
    base=(base*base)%mod;
    n>>=1;
}
return temp;    

}
/*
矩阵快速幂
m*m 的矩阵A 求他的n次幂
*/
const int MAXN=2;
const int MOD=1e4;//模为10000
typedef long long LL;
struct Matrx{

int m[MAXN][MAXN];
Matrx(){
    memset(m,0,sizeof(m));
}

};
Matrx Multi(Matrx a,Matrx b){//矩阵相乘
Matrx ans;
for(int i=0;i<MAXN;i++)

 for(int j=0;j<MAXN;j++)
  for(int k=0;k<MAXN;k++)
    ans.m[i][j]=(ans.m[i][j]+a.m[i][k]+b.m[k][j])%MOD;
    return ans;

}
Matrx fastm(Matrx a, int n){

Matrx res;
for(int i=0;i<MAXN;i++){
    //初始化为单位矩阵，相当于快速幂中的基数1;
    res.m[i][i]=1; 
}
while(n){
    if(n&1)res=Multi(res,a);
    a=Multi(a,a);
    n>>=1;    
}
return res;

}