快速幂算法

求a的n次幂

常规写法：

int qpow_2(int a, int n) { int ans = 1; while (n) { //n&1 与运算 可以判断n是否为偶数 如果是偶数，n&1返回0；否则返回1，为奇数。 if (n & 1) { ans *= a; } a *= a; n >>= 1;//n往右移一位 } return ans; }

利用分支思想，二分法求解：

int qpow(int a, int n) { if (n == 0) { return 1; } else if (n % 2 == 1) { return qpow(a, n - 1) * a; } else { int temp = qpow(a, n / 2); return temp * temp; } }

面对具体问题的实际应用：

斐波那契数列

求Fn mod 10^9 +7

#include <cstdio> #define MOD 1000000007 typedef long long ll; struct matrix { ll a1, a2, b1, b2; matrix(ll a1, ll a2, ll b1, ll b2) : a1(a1), a2(a2), b1(b1), b2(b2) {} matrix operator*(const matrix& y) { matrix ans((a1 * y.a1 + a2 * y.b1) % MOD, (a1 * y.a2 + a2 * y.b2) % MOD, (b1 * y.a1 + b2 * y.b1) % MOD, (b1 * y.a2 + b2 * y.b2) % MOD); return ans; } }; matrix qpow(matrix a, ll n) { matrix ans(1, 0, 0, 1); //单位矩阵 while (n) { if (n & 1) ans = ans * a; a = a * a; n >>= 1; } return ans; } int main() { ll x; matrix M(0, 1, 1, 1); scanf("%lld", &x); matrix ans = qpow(M, x - 1); printf("%lld\n", (ans.a1 + ans.a2) % MOD); return 0; }