数论学习笔记2——快速幂取模

2019-04-14 08:44发布

数论学习笔记2——快速幂取模

大佬肯定都是暴力循环乘出来的。
咳咳,考虑指数n在二进制下第A1Aj下为1,那么显而易见~ mn= i=1jmprod_{i=1}^jm(1<
由低位开始向前递推出每一位的m(1< 贴下代码: typedef long long ll; ll fastpow(ll x,ll y,ll mod) { ll ans=1; for(;y;y>>=1,x=x*x%mod) if(y&1) ans=ans*x%mod; return ans; }