快速幂

资料来源

以 $n^m$ 举例

由于指数 m 总能用二进制表示，而幂次上的加法就是多个指数幂次相乘

也就是说，当 $m = k_1+k_2+...+k_t$ 时（$k_i$表示 m 在二进制下第 i 位是 1 ），

每个 $n^m$ 都可以拆成 $n^{k_1+k_2+...+k_t} = n^{k_1} * n^{k_2} * ... * n^{k_t}$

所以我们就只需要求这里的 $k_1$，$k_2$，...，$k_t$

而求法就是 $m$ & $1$

需要注意的一点是：

　　aa 需要每次都平方，因为若现在次数为$n^8$，那么下一次就应该是$n^16$了，

　　这个转换是平方关系，所以每次都需要平方一下

上代码：

#include
#include
#define ll long long
using namespace std;
ll n,m;
ll big( ll a,ll b ){
    ll ans = 1,aa = a;
    while( b ){
        if( b & 1 ){ //二进制下为 1，应当乘上该位 
            ans *= aa;//乘上该位 
            printf( "ans = %ld  ",ans );
        }
        aa *= aa;//相当于 a^2，如现在取到了8次，那下一次就应当选16次 
        printf( "a = %ld  ",a ); 
        b >>= 1;
        printf( "b = %ld\n",b );
    }
    return ans;
}
int main(){
    cin >> n >> m;
    cout << big( n,m ); 
    return 0;
} 

需要模 p 的话，就去看资料来源吧