본문 바로가기

거듭제곱

 (3)
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의 나머지 연산 값을 구할 때 유용할 수 있겠다.
유사진법표기 엑셀컬럼 알파벳식 숫자표기법 http://synapsoft.co.kr/jsp/recruit/13_apply.html 10진법 표기법은 다음과 같다. N = a_n x 10^n + ... + a_1 x 10^1 + a_0 x 10^0 , a_i ∈ { 0 , ..., 9 }이 표기법으로는 0 이상의 모든 수를 표현할 수 있으며, 표기법은 유일하다. 이 표기법을 살짝 바꾼 표기법을 만들어 보면, N = a_n x 10^n + ... + a_1 x 10^1 + a_0 x 10^0 , a_i ∈ { 一 , ..., 九, 十 }이 표기법으로는 1 이상의 모든 수를 표현할 수 있으며 ( 0은 표기하지 못한다. ), 표기법은 유일하다. 심볼을 10개가 아닌 알파벳 대문자를 이용하면 26진법과 유사하게 26의 거듭제곱의 합으로 표현되는 표기법이 ..
[Euler Project 188] 1777의 1885 거듭거듭제곱의 마지막 8자리 구하기 거듭거듭제곱이란 단어는 tetration의 정확한 한국어 번역어를 몰라서 내가 개발한 번역임. 정확한 정의는 검색하여 보기바람. 매우 재미있음. #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=188 def phi(n0): ''' euler phi function for n, which consists of only 2 and 5 ''' n = n0 pow2 = 0 while n%2 == 0: n/=2 pow2 +=1 n = n0 pow5 = 0 while n%5 == 0: n/=5 pow5 +=1 if pow5 == 0: if pow2 == 0: return 1 else: return 2**(pow2-1) els..

티스토리툴바