数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究在 Python 中应用俄罗斯农民乘法原理的程序
假设我们得到了四个整数 p、q、r 和 k。我们将使用一种称为俄罗斯农民乘法的方法，并确定 (p + q.i)^r = r + s.i 的值。我们必须返回 r mod k 和 s mod k 的值。
因此，如果输入为 p = 3，q = 0，r = 8，k = 10000，则输出将为 (6561, 0) 3^8 = 6561，因为 q = 0，r mod k 的值为 6561。
为了解决这个问题，我们将按照以下步骤操作 −
- 如果 r 与 0 相同，那么
- 返回 1
- 否则当 r 与 1 相同时，那么
- 返回包含 (p mod k, q mod k) 的一对
- 否则当 r mod 2 是 0 时，那么
- 返回 solve((p*p - q*q) mod k, 2*p*q mod k, r/2, k)
- 否则，
- 一对 (pr, qr) = solve(p, q, r-1, k)
- 返回包含 ((p * pr - q * qr) mod k, (p * qr + q * pr) mod k) 的一对
示例
让我们看看以下实现以获得更好的理解 −
def solve(p, q, r, k):
if r == 0:
return 1
elif r == 1:
return (p % k, q % k)
elif r % 2 == 0:
return solve((p*p - q*q) % k, 2*p*q % k, r/2, k)
else:
(pr, qr) = solve(p, q, r-1, k)
return ((p * pr - q * qr) % k, (p * qr + q * pr) % k)
print(solve(3, 0, 8, 10000))输入
3, 0, 8, 10000
输出
(6561, 0)
更新于： 23-Oct-2021
420 次浏览
Advertisement