파이썬 백준 1629 곱셈

a, b, c = map(int, input().split())   bilist = [0 for i in range(31)] for i in range(30, -1, -1) :     bilist[i] = b // pow(2, i)     b = b - bilist[i] * pow(2, i) powerlist = [0 for i in range(31)] powerlist[0] = a % c for i in range(1, 31) :     powerlist[i] = pow(powerlist[i-1], 2) % c   remain = 1 for i in range(31) :     if bilist[i] == 1 :         remain = (remain * powerlist[i]) % c print(remain)

2^32 이하의 모든 자연수는 32자리 2진수로 표현된다. 즉, 2^i들의 합으로 표현할 수 있다.

그렇다면 a^b는 a^(2^i)들의 곱으로 표현할 수 있다.

 

b를 2진수 list bilist 형태로 바꾼다. bilist[i]가 0이라면 x_i가 0이고, 1이라면 x_i가 1인 셈이다.

 

다음으로 a(2^i)의 곱을 c로 나눈 나머지를 미리 저장해둘 powerlist를 만든다.

모듈러는 곱연산이 되므로, [0]번째에 a%c를 넣고 이전 값의 제곱을 c로 나누는 식으로 연쇄적으로 값을 구한다.

 

a^b는 위 Product 수식의 각 원소들의 곱이므로, a^b의 나머지는 각 원소들의 나머지의 곱의 나머지이다.

미리 작성한 bilist와 powerlist를 이용하여 각 원소들의 나머지를 연쇄적으로 곱해 답을 구한다.

 

b를 반토막씩 줄여가며 log b번의 재귀로 답을 구하는 것과 같은 방법인 것 같다.

미리 2진수 리스트를 작성해서 1의자리부터 올라갈지, 재귀함수를 짜서 절반씩 내려갈지 방법의 차이만 있다.