Funcia
Lv.2divide-and-conquermath

Modular Exponentiation

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

For each query [a, b, m] return ab mod ma^b \bmod m (with 00=10^0 = 1).

Examples

queriesresult
[[2, 10, 1000], [3, 0, 7], [10, 18, 7], [5, 3, 1]][24, 1, 1, 0]
[[7, 222, 13]][12]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(queries: long[][]) → long[]

Constraints

  • 1≤1 \le queries.length ≤100,000\le 100{,}000
  • 0≤a≤1090 \le a \le 10^9, 0≤b≤10180 \le b \le 10^{18}, 1≤m≤1091 \le m \le 10^9

Expected complexity

Time
O(Q log B)
Space
O(1)

Examples

queriesExpected
[[2,10,1000],[3,0,7],[10,18,7],[5,3,1]][24,1,1,0]
[[7,222,13]][12]

Hint

Hint

Square-and-multiply: square the base each step and multiply into the result where b has a 1 bit, reducing modulo m after every multiplication (products stay below 101810^{18}). Start from 1 % m. Multiplying b times exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)258 msestimated
C++ (GCC, gnu++23)258 msderived
Python 3.131000 msderived
Java 251638 msderived
Kotlin 2.4 (JVM)1516 msestimated
C# 14 (.NET 10)1516 msestimated

Test groups

GroupWeightTestsVisibility
sample02inputs and outputs
correctness405verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.