有一类题目是这样的

求 (x^y) % p

当y很大的时候，我们不能直接用for去一个一个的乘，因为这样的方法复杂度是O(N)的。那么有没有更高效的方法呢？

遇到这类问题的时候，我们就可以使用二分快速幂的方法来求解。
举个例子

3^7 = 3^4 * 3^2 *3^1

首先我们要知道，对于任意一个数s，它的二进制代表了它可以由2的次幂的累加和来表示。
比如7的二进制是111
那么它就是说 7 = 2^2 + 2^1 + 2^0
再比如一个数12的二进制是1101

13 = 2^3 + 2^2 + 2^0

所以对于任意一个x^y，我们都可以将y分解成2的幂次的形式。
例如5^13 = 5^8 * 5^4 * 5^1

这样做有什么好处呢？

1..2..4..8..16..32..64..128........1024.....

你发现其中的奥秘了吗？

1、每一个数都是它前一个数的2倍
2、它的迭代速度超级快

幂次方
题目描述：
对任意正整数N，求X^N%233333的值。
要求运算的时间复杂度为O(logN)。
例如
X30 = X15*X15
X15=X7*X7*X
X7=X3*X3*X
X3=X*X*X
共7次乘法运算完毕。
输入描述：
输入两个整数X和N，用空格隔开，其中X,N<=10^9。
输出描述：
输出X^N对233333取模的结果。
输入样例#:
2 5
输出样例#:
32
题目来源：
DreamJudge 1017

题目解析：运用上面讲过的二分快速幂思想和同余模定理即可。

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
typedef long long ll;  
ll mod_pow(ll x, ll y, ll mod) {  
    ll res = 1;  
    while (y > 0) {  
        //如果二进制最低位为1、则乘上x^(2^i)  
        if (y & 1) res = res * x % mod;  
        x = x * x % mod;  // 将x平方  
        y >>= 1;  
    }  
    return res;  
}  
  
int main() {  
    ll x, n;//注意x*x会超出int范围  
    scanf("%lld%lld", &x, &n);  
    printf("%lld\n", mod_pow(x, n, 233333));  
    return 0;  
}  

掌握二分快速幂