题解 | 算法竞赛进阶指南 a^b

思路

基本的快速幂.
首先我们知道 $x^a\times x^b = x^{a+b}$ .因此求 $a^b\%p$ 时对 $b$ 进行二进制拆分.
也就是将 $b$ 写成 $\sum 2^i[b \&2^i]$ 的形式.其中 $\&$ 表示位与, $[flg]$ 中的 $flg$ 为真时值为1,否则为0.
然后 $a^b$ 就变成了 $\prod a^{2^i[b\&2^i]}$ .
因为一个 $[1,N]$ 范围内的正整数二进制下最多只有 $O(\log N)$ 位,所以只要进行 $\log N$ 次运算就可以算出结果.
接下来是大家喜闻乐见的代码.

代码

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void cmax( T &x, T y ){ x < y ? x = y : x; }
template<typename T> inline void cmin( T &x, T y ){ y < x ? x = y : x; }
template<typename T>
inline void read( T &x ){ char t(getchar()), flg(0); x = 0;
    for ( ; !isdigit(t); t = getchar() ) flg = t == '-';
    for ( ; isdigit(t); t = getchar() ) x = x * 10 + ( t & 15 );
    flg ? x = -x : x;
}

clock_t t_bg, t_ed;

int a, b, p, ans(1);

int main(){
    t_bg = clock();
    read(a), read(b), read(p);
    for ( ; b; b >>= 1, a = 1ll * a * a % p ) if ( b & 1 ) ans = 1ll * ans * a % p;
    printf( "%d\n", ans % p );
    t_ed = clock();
    fprintf( stderr, "\n========info========\ntime : %.3f\n====================\n", (double)( t_ed - t_bg ) / CLOCKS_PER_SEC );
    return 0;
}