Nhân số phức bằng phương pháp Russian Peasant trong Python

Cho p, q, r, k. Tính (p + q*i)^r = R + S*i. Trả về R mod k và S mod k. Sử dụng phương pháp Russian Peasant (nhân nhanh).

Ví dụ: p=3, q=0, r=8, k=10000 → (6561, 0).

Giải thuật

• Đệ quy:
  • r=0: trả về 1 (số thực 1).
  • r=1: trả về (p%k, q%k).
  • r chẵn: tính (p+qi)^(r/2) rồi bình phương.
  • r lẻ: tính (p+qi)^(r-1) rồi nhân với (p+qi).
• Mọi phép toán lấy modulo k.

Ví dụ mã Python

def solve(p, q, r, k):
    if r == 0:
        return (1 % k, 0)
    elif r == 1:
        return (p % k, q % k)
    elif r % 2 == 0:
        # square
        pr, qr = solve(p, q, r // 2, k)
        return ((pr*pr - qr*qr) % k, (2*pr*qr) % 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))  # Output: (6561, 0)

Đầu vào

3, 0, 8, 10000

Đầu ra

(6561, 0)