问题 D: 取余运算

题目描述

输入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)))

使用到的理论：

模运算规则：
$$\begin{gathered} (a\times b)\%n=(a\%n\times b\%n)\%n \\ {a}^b\%n=((a\%n{)}^b)\%n \end{gathered}$$
递推公式：
$$a^p\%k=\{\begin{array}{ll}a\%k& \text{(p=1)}\\ (a\times a^{p-1}\%k)\%k& \text{(p是奇数)}\\ ((a\times a)\%k{)}^{p/2}\%k& \text{(p是偶数)}\end{array}$$

答案不唯一，必定有更加优化的解法欢迎分享