快速幂

xiufanivan · 2023-04-03 16:58:58 · 个人记录

题目描述：

求 a^b\%c 的值。其中 a,b,c 是整数，且 0 < a,c < 10^9, 0 < b < 10^{18} 。

#include <bits/stdc++.h>
using namespace std;

long long fast_power(long long a, long long b, long long c) {
    long long ans = 1;
    a %= c;
    while (b) {
        if (b & 1) {  // b % 2 == 1, 奇数 
            ans = (ans * a) % c;
        }
        a = (a * a) % c;
        b >>= 1;  // b /= 2 
    }
    return ans;
}

int main() {

    cout << fast_power(2, 5, 7) << endl;  // 2^5 % 7 = 4

    return 0;
}