快速幂

使用方法

  1. 使用命名空间

    using namespace algorithm
    
  2. 然后直接使用函数即可

函数说明

函数Type pow(Type index, Type head) 计算 indexheadindex^{head} 的值,返回值为Type类型

函数Type pow(Type index, Type head, Type mod) 计算 indexhead  %  modindex^{head}\ \ \%\ \ mod 的值,返回值为Type类型


模板代码

namespace algorithm{
    template <class Type>
    Type qpow(Type index, Type head, Type mod = (Type)-1){
        Type sum = (Type)1;
        while(head){
            if(head & 1){
                sum = sum * index;
                if(mod != -1)    sum %= mod;
            }
            head >>= 1;
            index = index * index;
            if(mod != -1)    index %= mod;
        }
        return sum;
    }
}