快速幂+矩阵快速幂

佚名 6年前 (2019-04-13) 随笔 1182人围观抢沙发百度已收录

一. 快速幂入门

相关博客：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

https://www.cnblogs.com/CXCXCXC/p/4641812.html

https://www.cnblogs.com/vincent-hwh/p/5990331.html

二进制位运算：

由于是二进制，很自然地想到用位运算这个强大的工具：&和>>

&运算通常用于二进制取位操作，例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶x&1==0为偶，x&1==1为奇。 >>运算比较简单二进制去掉最后一位

 1 int poww(int a,int b)
 2 {
 3     int base=a;
 4     long long ans=1;
 5     while(b>0)
 6     {
 7         if(b&1!=0)//判断为奇数 
 8         ans*=base;
 9         base*=base;
10         b>>=1;//位运算，类似于开平方根，但是对b=1处理时b>>=1,b的值是0，若是平方仍为1 
11     }
12     return ans; 
13 }

 1 int poww(int base,int b,int mod)  //(base^b)%mod 
 2 {
 3     long long ans=1;
 4     while(b>0)
 5     {
 6         if(b&1!=0)//判断为奇数 
 7         ans=(ans*base)%mod;
 8         base=(base*base)%mod;
 9         b>>=1;//位运算，类似于开平方根，但是对b=1处理时b>>=1,b的值是0，若是平方仍为1 
10     }
11     return ans; 
12 }