每日算法——数的幂次

关键词

快速幂

题目描述

给定三个正整数 N, M, P, 求 N^M\mod P.

输入描述

第1行为一个整数 T，表示测试数据数量。

接下来的 T 行每行包含三个正整数 N, M, P。

1 \leq T \leq 10^5, 1 \leq N, M, P \leq 10^9。

输出描述

输出共 T 行，每行包含一个整数，表示答案。

示例

输入

3
2 3 7
4 5 6
5 2 9

输出

1
4
7

知识点

将十进制数 n 写成二进制形式为 (n_tn_{t-1}...n_1n_0)_2，那么有 n=n_t2^t+n_{t-1}2^{t-1}+n_{t-2}2^{t-2}+...+n_12^1+n_02^0，其中 n_i \in \{0, 1\}。那么就有

\begin{aligned}a^n &= (a^{n_t2^t+...+n_02^0}) \\ &= a^{n_02^0} \times a^{n_12^1} \times ... \times a^{n_t2^t}\end{aligned}

这个算法的时间复杂度为 \Theta(\log n)。

解决方案

快速幂

long long fast(int n, int m, int p){
    long long a = n, t = 1;
    while (m > 0){
        if (m & 1) t = t * a % p;
        a = a * a % p;
        m /= 2;
    }
    return t;
}