算法题：快速模幂

问题描述

试求a^b%n的值，其中a,b,n均为long long范围内的数。

输入格式

三个整数即a,b,n。

输出格式

输出结果。

样例

输入

2 3 9

输出

8

解决方案

思路

快速幂

代码

#include <iostream>

using namespace std;

//(a^b)%mod
long long pow_ex(long long a, long long b, long long mod) {
    long long result = 1 % mod;

    a %= mod;
    while (b) {
        if (b & 1) {
            result *= a;
            result %= mod;
        }
        a *= a;
        a %= mod;

        b >>= 1;
    }

    return result;
}

int main() {
    long long a, b, n;
    cin >> a >> b >> n;

    cout << pow_ex(a, b, n);

    return 0;
}