老年人记忆力差体谅一下...

//快速幂的两种写法
 
//递归写法
typedef long long LL;
LL binarypow(LL a, LL b,LL m)//求a^b%m 
{
    if(b==0) return 1;//递归边界
    if(b%2==1) return a*binarypow(a,b-1,m);
    else
    {
        LL mul=binarypow(a,b/2,m);
        return mul*mul%m;
     } 
 }
 
//迭代写法
typedef long long LL;
LL binarypow(LL a, LL b, LL m)
{
    LL ans=1;
    while(b>0)
    {
        if(b&1)//用来判断b的末位是否1,也可用来判断b是否为奇数,
               //若按位与后为0,则为偶数(偶数的二进制最后一位一定为0),为1为奇数 
        {
            ans=ans*a%m;
        }
        a=a*a%m;
        b>>=1//将b的二进制右移一位,即b=b>>1或b=b/2 
    }
    return ans;
 }
Last modification:December 10th, 2020 at 03:05 pm