快速幂（二进制优化）

快速幂介绍快速幂是用了二进制优化。模板题P1226 【模板】快速幂#includebits/stdc.husingnamespacestd;#defineintlonglongintfast_pow(inta,intb,intmod)//分别是底数、幂次、模式{intans1;//答案while(b){if(b1){ans(ans*a)%mod;}aa*a%mod;//aa^2b1;}returnans;}signedmain(){inta,b,p;cinabp;printf(%d^%d mod %d%d,a,b,p,fast_pow(a,b,p));return0;}比如a10,b10,mod145141919810。b( 1010 ) 2 (1010)_2(1010)2​所以a b a 10 a 2 1 × a 2 3 a^ba^{10}a^{2^1}\times a^{2^3}aba10a21×a23可以把时间复杂度优化到O ( l o g n ) O(logn)O(logn)模板代码intfast_pow(inta,intb,intmod){intans1;while(b){if(b1){ans(ans*a)%mod;}aa*a%mod;b1;}returnans;}