Giả sử chúng ta được cho bốn số nguyên p, q, r và k. Chúng tôi sẽ sử dụng một phương pháp được gọi là phương pháp Nhân nông dân Nga và xác định giá trị của (p + q.i) ^ r =r + s.i. Chúng ta phải trả về giá trị của r mod k và s mod k.
Vì vậy, nếu đầu vào là p =3, q =0, r =8, k =10000, thì đầu ra sẽ là (6561, 0) 3 ^ 8 =6561, như giá trị q =0 của r mod k =6561 .
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- nếu r giống 0, thì
- trả lại 1
- theo chiều kim khi r giống với 1, thì
- trả về một cặp chứa (p mod k, q mod k)
- theo chiều kim khi r mod 2 giống 0, thì
- trả về giải quyết ((p * p - q * q) mod k, 2 * p * q mod k, r / 2, k)
- theo chiều dọc,
- một cặp (pr, qr) =giải quyết (p, q, r-1, k)
- trả về một cặp chứa ((p * pr - q * qr) mod k, (p * qr + q * pr) mod k)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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)) Đầu vào
3, 0, 8, 10000
Đầu ra
(6561, 0)