โปรแกรมใช้วิธี Russian Peasant Multiplication สำหรับจำนวน מרוכบใน Python

ได้รับ p, q, r, k ต้องการคำนวณ (p + q*i)^r = real + imag*i แล้วคืนค่า (real mod k, imag mod k) ใช้วิธี Russian Peasant Multiplication (ยกกำลังแบบทวินิพจน์)

ตัวอย่าง: p=3, q=0, r=8, k=10000 → (6561, 0)

ขั้นตอนการแก้ปัญหา

ใช้การยกกำลังแบบแบ่งครึ่ง (exponentiation by squaring) สำหรับจำนวน מרוכบ:

1. ฐาน: r=0 → (1,0); r=1 → (p%k, q%k)
2. รหัสคู่: คำนวณ (p+qi)^(r/2) แล้วยกกำลังสอง
3. รหัสคี่: คำนวณ (p+qi)^(r-1) แล้วคูณกับ (p+qi)

ตัวอย่างโค้ด Python

def solve(p, q, r, k):
    if r == 0:
        return (1, 0)
    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))  # ผลลัพธ์: (6561, 0)

อินพุตตัวอย่าง

3, 0, 8, 10000

เอาต์พุตตัวอย่าง

(6561, 0)