在 Python 中应用俄罗斯农民乘法的程序

pythonserver side programmingprogramming更新于 2026/1/31 8:12:17

假设我们给出了四个整数 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))