快速幂(模版)
//求x^y%mod ll quick(ll x,ll y,ll mod){ ll ans=1; while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y/=2; } return ans; }
//求a^n%mod (mod 在前面定义了) ll quick(ll a,ll n) { ll re=1; while(n) { if(n&1) //判断n的二进制最后一位是不是1,或者说判断n是不是奇数 { re=(re*a)%mod; } n>>=1; //除掉n二进制的最后一位,相当于/2 a=(a*a)%mod; } return re%mod; }
//快速幂取余全都用long long不固定代码: long long quick(long long x,long long y,long long n) { long long ans=1; while(y) { if(y%2==1) ans=ans*x%n; x=x*x%n; y/=2; } return ans; }
不知道为啥,现在才整理快速幂的相关知识,很多东西还是整理下来吧,方便以后的学习跟总结。
简单的相关知识:
1.&(按位与运算符)
x&1==1,则表示x为奇数;
x&1==0,则表示x为偶数;
2.>> <<(移位运算符)
"<<" :左移
">>" :右移
数学意义:右移移位相当于除以2,右移n位相当于除以2^n。左移同理
例如:11>>2=2(11换成二进制:1011,右移两位为10,换成十进制为2)
先举一个最简单的例子:2^13 = 2^(1101) = 2^8 * 2^4 * 2^1 快速幂代码:求a^n ll qpow(ll a,ll n) { ll re=1; while(n) { if(n&1) //判断n的二进制最后一位是不是1,或者说判断n是不是奇数 { re=(re*a)%mod; } n>>=1; //除掉n二进制的最后一位 a=(a*a)%mod; } return re%mod; }
模版专项 文章被收录于专栏
模版