1. 문제 2247번: 실질적 약수 (acmicpc.net) 2247번: 실질적 약수 첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1부터 n까지 각각 약수들 중 1과 자기 자신을 제외한 약수들의 합들의 누적합을 구하는 문제 2. 방법1 가장 쉬운 방법은 1부터 n까지 순회해서 각 자연수를 i라고 한 다음, i에 대한 모든 약수를 구해서 1과 자기 자신을 제외하고 더하면 된다 약수는 $O(\sqrt{n})$ 알고리즘으로 모두 나눠보는 방식으로 구한다 그런데 p = 1부터 시작하면, i를 1로 나누면 1과 i를 더하게 되는데 실질적 약수라면 1과 i를 제외한 나머지들의 합을 구해야하니 p = 2부터 시작하는게 핵심 n = int(input()) ans..
1. 문제 1565번: 수학 (acmicpc.net) 1565번: 수학 배열 D와, 배열 M이 주어졌을 때, D에 있는 모든 수의 배수이며, M에 있는 모든 수의 약수인 수의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 수들의 최소공배수의 배수는, 모든 수들의 공배수이며, 수들의 최대공약수의 약수는, 모든 수들의 공약수이다. M에서 최대공약수를 구한 다음에, 최대공약수의 약수들을 구한다. $O(\sqrt{N})$으로 구할 수 있다. 여기서 set()을 이용해서 중복을 피해준다 다음 D에서 최소공배수를 구해준다. a,b의 최소공배수는 a*b/gcd(a,b)로 구할 수 있 그리고 M에서 구한 약수들이 최소공배수의 배수인지 판단해준다 from sys import stdin de..
1. 문제 25333번: 개구리 (acmicpc.net) 25333번: 개구리 Albert는 개구리 장난감을 이용한 놀이를 즐겨한다. 이 장난감은 우측으로 $A$cm 혹은 좌측으로 $B$cm 점프할 수 있다. 예를 들어 현재 개구리 장난감의 위치가 $0$이고 $A = 4$, $B = 2$ 라 하자. 아래 그 www.acmicpc.net 2. 풀이 예제를 보면 A,B의 최대공약수의 배수의 개수가 정답일 것 같은데 조금 수학적으로 생각해보면 A,B로 만들 수 있는 자연수가 X 이내에 몇개나 있느냐?라는 문제와 같은데 오른쪽으로 x번 A만큼 점프하면 Ax가 되고 왼쪽으로 y번 B만큼 점프하면 By가 되니까, 만들 수 있는 정수는 Ax+By형태와 같다. 이는 베주의 항등식 형태와 같으며, "정수 x,y에 대하여..
1. 피보나치 수열 $F_{0} = 0, F_{1} = 1, F_{n} = F_{n-1}+F_{n-2}, n \geq 2$로 정의되는 수열 $F_{n}$ 2. 홀수번째 항의 합 1항부터 $2n-1$번째 항까지의 합은 다음과 같이 $2n$번째 항과 동일하다. $$\sum_{k = 1}^{n} F_{2k-1} = F_{2n}$$ 증명) $F_{n+2} = F_{n+1} + F_{n}$에서 n = 2n - 2를 대입하면, $F_{2n} = F_{2n-1} + F_{2n-2}$ 그러면, $F_{2n-1} = F_{2n} - F_{2n-2}$이므로, $$\sum_{k=1}^{n} F_{2k-1} = F_{1} + \sum_{k=2}^{n} (F_{2k} - F_{2k-2})$$ 이 식을 풀어서 써보면, 망원급수임..
1. 피보나치 수의 최대공약수 다음과 같이 정의되는 피보나치 수열 $F_{0} = 0, F_{1} = 1$이고 $F_{n+2} = F_{n+1} + F_{n}, n \geq 0$ 에 대하여, n번째 피보나치 수 $F_{n}$와 m번째 피보나치 수 $F_{m}$의 최대공약수 $gcd(F_{n}, F_{m})$은 n,m의 최대공약수 gcd(n,m)번째 피보나치 수와 같다. $$gcd(F_{n}, F_{m}) = F_{gcd(n,m)}$$ 2. 보조정리1 임의의 정수 k에 대하여, $gcd(a,b) = gcd(a+kb, b)$ 증명) x가 a,b의 공약수라면, a는 x로 나누어 떨어지고 ($x | a$로 표시) b도 x로 나누어 떨어진다. 그러므로, 임의의 정수 k에 대하여 kb도 x로 나누어 떨어진다. a도..
1. 피보나치 수 피보나치 수열 $F_{n}$을 다음과 같이 정의하고, $F_{n}$을 피보나치 수라고 하자. $F_{0} = 0, F_{1} = F_{2} = 1$, $F_{n} = F_{n-1} + F_{n-2}, n \geq 2$ 두 피보나치 수 $F_{m}$과 $F_{n}$에 대하여 m = n+1 혹은 m = n-1이면 두 피보나치 수가 인접하다고 한다. 즉, $F_{n+1}$과 $F_{n}$은 인접한 피보나치 수이며 $F_{n}$과 $F_{n-1}$은 인접한 피보나치 수이다. 2. 제켄도르프의 정리(Zeckendorf's theorem) "모든 자연수는 인접하지 않은 피보나치 수($F_{0}$, $F_{1}$을 제외한)들의 합으로 표현할 수 있으며, 그 표현 방법이 유일하다" 예를 들어 n = ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
