快速幂取模

一、递归法

typedef long long LL； LL binaryPow(LL a, LL b, LL m) { if(b==1) return 1; if (b&1) return a*binaryPow(a,b-1,m)%m else { int num; num=binaryPow(a,b/2,m); return num*num%m; } }

当b为偶数时，不能直接返回binaryPow(a,b/2,m)*binaryPow(a,b/2,m) 这样会调用两次 增加时间复杂度

二、迭代法 对于 a^b来说，如果将b写成二进制，那么b可以写成若干个二进制之和 那么a^{b可以变为多个a}2^i的积 如a的13次幂 13转化成2进制数为1101 所以a^13=a2^3*a2²a²0;

typedef long long LL； LL binaryPow(LL a, LL b, LL m) { LL ans=1；//存储累积的结果 while(b!=0) { if(b%2==1) { ans=ans*a%m; } a=a*a%m; b=b/2; } return ans; }