AcWing 875 快速幂的算法原理是什么？
- 内容介绍
- 文章标签
- 相关推荐
本文共计394个文字，预计阅读时间需要2分钟。
题目：模幂运算给定：$n$，组+$a_i, b_i, p_i$，对于每组数据，求出$ a_i^{b_i} \mod p_i $的值。输入格式：第一行包含一个整数$n$。接下来$n$行，每行包含三个整数$a_i, b_i, p_i$。输出格式：对于每组数据，输出一个结果，每个结果占一行。
题目
给定 $n$ 组 $a_i,b_i,p_i$，对于每组数据，求出 ${a_i}^{b_i}mod{p_i}$ 的值。
输入格式 第一行包含整数 $n$。
接下来 $n$ 行，每行包含三个整数 $a_i,b_i,p_i$。
输出格式 对于每组数据，输出一个结果，表示 ${a_i}^{b_i}mod{p_i}$ 的值。
每个结果占一行。
数据范围 $1≤n≤100000,1≤a_i,b_i,p_i≤2×10^9$ 输入样例：
2
3 2 5
4 3 9
输出样例：
4
1
思路
主要思路是将 $b$ 转换成二进制，将二进制中位为 $1$ 的初始化，最终结果由预处理的数值拼凑而成。
本文共计394个文字，预计阅读时间需要2分钟。
题目：模幂运算给定：$n$，组+$a_i, b_i, p_i$，对于每组数据，求出$ a_i^{b_i} \mod p_i $的值。输入格式：第一行包含一个整数$n$。接下来$n$行，每行包含三个整数$a_i, b_i, p_i$。输出格式：对于每组数据，输出一个结果，每个结果占一行。
题目
给定 $n$ 组 $a_i,b_i,p_i$，对于每组数据，求出 ${a_i}^{b_i}mod{p_i}$ 的值。
输入格式 第一行包含整数 $n$。
接下来 $n$ 行，每行包含三个整数 $a_i,b_i,p_i$。
输出格式 对于每组数据，输出一个结果，表示 ${a_i}^{b_i}mod{p_i}$ 的值。
每个结果占一行。
数据范围 $1≤n≤100000,1≤a_i,b_i,p_i≤2×10^9$ 输入样例：
2
3 2 5
4 3 9
输出样例：
4
1
思路
主要思路是将 $b$ 转换成二进制，将二进制中位为 $1$ 的初始化，最终结果由预处理的数值拼凑而成。