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;
}
评论