414. 快速幂
时间限制：1000 MS 内存限制：64 MB
题目描述
# 快速幂 ## 题目描述 给定 $n$ 组整数 $a_i,b_i,p_i$，对于每组数据，求出 $a_i^{b_i} \bmod p_i$ 的值，即 $a_i^{b_i}$ 除以 $p_i$ 所得的非负余数。 ## 输入格式 从文件 `qpow.in` 中读入数据。 第一行包含一个整数 $n$，表示数据的组数。 接下来 $n$ 行，每行包含三个整数 $a_i,b_i,p_i$。 ## 输出格式 将结果输出到文件 `qpow.out` 中。 输出 $n$ 行，第 $i$ 行包含一个整数，表示 $a_i^{b_i} \bmod p_i$ 的值。 ## 数据范围 对于所有测试数据： - $1 \le n \le 100000$； - $1 \le a_i,b_i,p_i \le 2\times 10^9$。 ## 样例输入 ``` 2 3 2 5 4 3 9 ``` ## 样例输出 ``` 4 1 ``` ## 运行限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。