큰승수 (1) 썸네일형 리스트형 pow(a, n) for n is large def pow(a, n):k = 1a_pow_k = aa_pow_n = 1while n:if k & n:a_pow_n *= a_pow_kn -= ka_pow_k = a_pow_k ** 2k *= 2return a_pow_n an = aklmno = ak0000 al000 am00 an0 ao 위 식에서 klmno 는 n의 2진수 표현. 즉, a2k 들의 곱만으로 an 을 쪼갤 수 있고,a2k 는 a2k-1의 제곱이므로, 위 함수와 같이 빠르게 an 을 구할 수 있다. 위 함수는 변형하여 an의 나머지 연산 값을 구할 때 유용할 수 있겠다. 이전 1 다음