পাইথনে রাশিয়ান পিজান্ট মাল্টিপ্লিকেশন দিয়ে কমপ্লেক্স সংখ্যা ঘাত করা

চার ইন্টিজার 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⁸ = 6561, q = 0 হলে ইমেজিনারি পার্ট ০।

সমাধান পদ্ধতি

1. যদি r == 0: ১ রিটার্ন করুন।
2. যদি r == 1: (p % k, q % k) রিটার্ন করুন।
3. যদি r % 2 == 0: রিকার্সিভ কল solve((p*p - q*q) % k, 2*p*q % k, r/2, k)
4. অন্যথায়:
   • (pr, qr) = solve(p, q, r-1, k)
   • রিটার্ন ((p*pr - q*qr) % k, (p*qr + q*pr) % 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))  # আউটপুট: (6561, 0)

ইনপুট

3, 0, 8, 10000

আউটপুট

(6561, 0)