CSES - Exponentiation II

Author: Ryan Chou

Appears In

Gold - Modular Arithmetic

Explanation

Fermat's Little Theorem tells us that $a^{p - 1} \equiv 1 \pmod{p}$ , so we can calculate $a^{b^c \pmod{1e9 + 7 - 1}} \pmod{1e9+7}$ with modular exponentiation.

Implementation

Time Complexity: $\mathcal{O}(\log P)$

C++

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

using ll = long long;
const ll MOD = 1e9 + 7;

 Code Snippet: Binary Exponentiation (Click to expand)

int main() {
	int test_num;

Python

MOD = int(1e9) + 7

for _ in range(int(input())):
	a, b, c = map(int, input().split())
	pow_bc = pow(b, c, MOD - 1)
	print(pow(a, pow_bc, mod))

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!