피사노 주기 계산하기 - 15 곱하기 10의 n-1 승
피사노 주기 Pisano Period피보나치 수열을 어떤 자연수 m 으로 나눈 나머지들이 다시 처음 상태(0, 1, ..) 로 돌아오기까지의 최소 양의 길이 피보나치 수열을$$ F_{0} = 0, F_{1} = 1, F_{n} = F_{n−1} + F_{n−2} $$ 라고 할 때,$$ \pi(m) = \min \{\, k > 0 \mid (F_k \bmod m,\; F_{k+1} \bmod m) = (0,1) \,\} $$ 기준이 (0, 1) 인 이유는 피보나치 수열의 맨 앞 두 항이 0과 1이기 때문이다.그래서 0과 1이 재등장하면, 그 전까지가 (피사노) 주기가 되는 것이다. # 의사코드prev = 0curr = 1for i = 1 to ∞: next = (prev + curr) mod..
2026. 2. 6.
유클리드 호제법 - 최대공약수, 최소공배수 구하기
유클리드 호제법두 숫자 a, b (a > b)가 있을 때,{a를 b로 나눈 나머지 r 과 b}의 최대 공약수는 {a와 b} 의 최대 공약수가 같다. * GCD (Greatest Common Divisior) : 최대 공약수GCD(a, b) = GCD(b, r)위 식을 반복해서 구하고, r = 0 일 때의 b 값이 최대공약수이다. python 으로 최대공약수, 최소공배수 구하기# 최대 공약수 구하기def gcd(a, b): while b > 0: a, b = b, a % b return a # 최소 공배수 구하기def lcm(a, b): return a * b / gcd(a, b)
2026. 2. 5.
