题目描述
输入b，p，k的值，求b^p mod k的值（即b的p次方除以k的余数）。其中b，p，k*k为32位整数。
输入
输入b，p，k的值
输出
输出b^p mod k的值
样例输入
2 10 9
样例输出
2^10 mod 9=7
解答（分治算法）：
def mod(b, p, k):
if p == 1:
return b % k
if p % 2:
return mod(b % k, p - 1, k) * b % k # p是奇数
else:
return mod((b * b) % k, p // 2, k) # p是偶数
b1, p1, k1 = map(int, input().split())
print("%d^%d mod %d=%d" % (b1, p1, k1, mod(b1, p1, k1)))
使用到的理论：
模运算规则：
(
a
×
b
)
%
n
=
(
a
%
n
×
b
%
n
)
%
n
a
b
%
n
=
(
(
a
%
n
)
b
)
%
n
(a times b) % n=(a %n times b % n) %n \[2ex] a^b %n=((a %n)^b) %n
(a×b)%n=(a%n×b%n)%nab%n=((a%n)b)%n
递推公式：
a
p
%
k
=
{
a
%
k
(p=1)
(
a
×
a
p
−
1
%
k
)
%
k
(p是奇数)
(
(
a
×
a
)
%
k
)
p
/
2
%
k
(p是偶数)
a^p %k= begin{cases} a %k &text{(p=1)}\[2ex] (a times a^{p-1} %k) %k &text{(p是奇数)}\[2ex] ((a times a)%k)^{p/2} %k &text{(p是偶数)} end{cases}
ap%k=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧a%k(a×ap−1%k)%k((a×a)%k)p/2%k(p=1)(p是奇数)(p是偶数)
答案不唯一，必定有更加优化的解法欢迎分享
