네 개의 정수 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과 같을 때
- 복귀 풀기((p*p - q*q) mod k, 2*p*q mod k, r/2, k)
- 그렇지 않으면
- 쌍(pr, qr) =해결(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)) 입력
3, 0, 8, 10000
출력
(6561, 0)