题解 | #华华教月月做数学#
华华教月月做数学
https://ac.nowcoder.com/acm/problem/23046
技巧
快速幂
思路
数学性质 如 7^10 = 7^5 * 7^5
7^5 = 7^2 * 7^2 * 7^1
这里要注意 两个大数字直接相乘然后取模可能会爆掉 需要把乘法转换成加法一次一次的运算取模
相乘的话 例如 3 * 5 （011 * 101） 代表3个5 相加。 101可以看成 1个3 和4个3相加 循环时候a保持倍增即可
实现
package main
import (
"bufio"
. "fmt"
"io"
"os"
)
// 乘法转加法每次都mod 防止a*b爆掉
func mul(a, b ,mod int) int{
ans := 0
for b != 0 {
if b & 1 == 1 {
ans = (ans + a) % mod
}
a = (a + a) % mod
b >>= 1
}
return ans
}
// 快速幂模板 - 循环
func qpow(A, B, P int) int{
ans := 1
for B != 0 {
if (B & 1) != 0 {
ans = mul(ans, A, P)
}
A = mul(A, A, P)
B >>=1
}
return ans
}
// 快速幂模板 - 递归
func qpow1(A, B, P int) int{
if B == 0 {
return 1
}
if B % 2 == 1 {
return mul(qpow1(A, B-1, P), A, P)
}else {
tmp := qpow1(A, B/2,P)
return mul(tmp, tmp, P)
}
}
// https://ac.nowcoder.com/acm/problem/23046
func NC23046(_r io.Reader, _w io.Writer) {
in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
defer out.Flush()
var T int
for Fscan(in, &T); T > 0; T-- {
var A, B, P int
Fscan(in, &A, &B, &P)
Fprintln(out, qpow1(A,B,P))
}
}
func main() {
NC23046(os.Stdin, os.Stdout)
}
