class="markdown_views prism-github-gist">

求a的b次方对p取模的值，其中 1 ≤ a,b,p ≤ $10^9$

10^9次运算，会超时，得用快速幂。 什么是快速幂呢？ 就是快速的幂运算。快速幂会将运算划分为$logn$次运算，并且每一次的运算都能够运用到上一次运算的计算结果。 比如计算$a^{11}$时，
因为11的二进制为1011，即${2^3}cdot1+ {2^2}cdot0 + {2^1}cdot1 + {2^0}cdot1 =11$
所以我们把它拆成$a^{11} = a^8 cdot a^2 cdot a^1$。
原本$a^{11}$操作是11次乘法运算，现在可以转化为3(即$logn$)次乘法运算，
其中每一个乘项都可以通过前一个已经得到计算结果的乘项通过位运算很快地计算，整体也就很快。 即 $a^{11}=(1 imes {a^2}^3) imes (0 imes {a^2}^2) imes (1 imes {a^2}^1) imes(1 imes {a^2}^0)$ 附：模运算公式。

模运算与基本四则运算有些相似，但是除法例外。其规则如下：
(a + b) % p = (a % p + b % p) % p （1）
(a – b) % p = (a % p – b % p) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
(a^b) % p = ((a % p)^b) % p （4）
结合律：
((a+b) % p + c) % p = (a + (b+c) % p) % p （5）
((ab) % p * c)% p = (a * (bc) % p) % p （6）
交换律：
(a + b) % p = (b+a) % p （7）
(a * b) % p = (b * a) % p （8）
分配律：
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9）
重要定理：
若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（10）
若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；（11）
若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a – c) ≡ (b – d) (%p)，
(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)； （12）

此外，因为两个32位int相乘可能会溢出，可以强制转化位long long，在赋值操作时还原为int。 #include using namespace std; int a, b, p; // (a ^ b) mod p int power() { int ans = 1 % p; // %p 是防止b=0。b=0时应该输出0 for (; b; b >>= 1) { if (b & 1) ans = (long long)ans * a % p; a = (long long)a * a % p; } return ans; } int main() { cin >> a >> b >> p; cout << power() << endl; return 0; } 上面的代码中，通过右移>> ，与& 两个运算的结合，遍历了b的二进制表示下的每一位。
在循环到第i次时（从0开始计数），变量a中存储的是${a^2}^i$，若b当前位为1，则把此时的变量b积累到答案ans中。

---

求a乘b对p取模的值，其中1≤a,b,p≤$10^{18}$

数据范围为18次方，会超时。需要用快速乘，和快速幂一样，快速乘会将运算划分为$logn$次运算，并且每一次的运算都能够运用到上一次运算的计算结果。 把快速幂的次方换成这里的乘积，相应的ans*a变成ans+a
例如求$a imes 11 = a imes8 + a imes2+ a imes1$
即 $a imes 11=(a imes 1 imes 2 imes2 imes2)+ (a imes 0 imes2 imes2)+(a imes 1 imes2)+(a imes 1 imes1)$ #include typedef long long ll; using namespace std; ll a, b, p; ll mul() { long long ans = 0; for (; b; b >>= 1) { if (b & 1) ans = (ans + a) % p; a = a * 2 % p; } return ans; } int main() { cin >> a >> b >> p; cout << mul() << endl; return 0; }