1. 문제 1750번: 서로소의 개수 (acmicpc.net) 1750번: 서로소의 개수 예제 1의 경우 가능한 경우의 수는 (2, 3), (4, 3), (2, 4, 3)이다. www.acmicpc.net 2. 풀이 수열에서 어떤 원소는 선택하고 어떤 원소는 선택하지 않아 만든 부분집합의 원소들의 최대공약수가 1이 되는 부분집합의 개수를 구하는 문제 안풀어보면 대단히 어렵다. dp[i][j]를 배열의 i번째 수까지 사용했을때, 최대공약수가 j가 되는 부분집합의 개수라고 정의 원소의 크기는 10만까지니까 최대공약수도 당연히 10만까지 가능할거고 여기서 중요한건 자기 자신만 사용하면 최대공약수는 자기 자신이다 초기화할때는 모든 i = 0,1,2,...,n-1에 대하여 dp[i][s[i]] = 1 이게 무슨말..
1. 문제 11414번: LCM (acmicpc.net) 11414번: LCM 두 자연수 A, B가 주어졌을 때, A + N과 B + N의 최소공배수가 최소가 되는 자연수 N을 구하시오. www.acmicpc.net 2. 풀이 임의의 정수 k에 대하여 $$gcd(a,b) = gcd(a+kb,b)$$를 이용하자. 그러면, $$gcd(a+n, b+n) = gcd(a-b, b+n) = gcd(a+n, b-a)$$를 얻는다. 그래서 a < b이면, $a+n \leq gcd(a+n,b+n) \leq b-a$ 최대공약수로 gcd(a+n,b+n) = gcd(a-b,b+n) = gcd(b-a,b+n) = b-a라고 한다면... (gcd(a,b) = gcd(abs(a),abs(b))이기 때문) b+n이 b-a의 배수라는..
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. 피보나치 수의 최대공약수 다음과 같이 정의되는 피보나치 수열 $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. 문제 25342번: 최대 최소공배수 (acmicpc.net) 25342번: 최대 최소공배수 $N = 3$인 경우, $1, 2, 3$을 선택하면 최소공배수는 $6$이다. $N = 4$인 경우, $2, 3, 4$를 선택하면 최소공배수는 $12$이다. www.acmicpc.net 2. 풀이 3개의 수의 최소공배수가 최대가 될려면 어떻게 해야할까 두 수 a,b의 최소공배수는? a = Gn이고 b = Gm으로 표현할 수 있다면(G는 a,b의 최대공약수, n,m이 서로소) a,b의 최소공배수는 L = Gnm이다. 이 최소공배수가 가장 클려면 어떻게 해야할까? L = Gnm이므로, L = am이거나 L = bn으로 표현할 수 있다. 이 둘은 모두 ab보다 작거나 같다. 따라서, L
1. 문제 2436번: 공약수 (acmicpc.net) 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 2. 풀이 최대공약수 G, 최소공배수 L이 주어질때 두 수 x,y는 어떻게 구할까 $$x = Gk_{1}$$ $$y = Gk_{2}$$ 이 때 L은 다음과 같이 구할 수 있다 $$L = Gk_{1}k_{2}$$ 따라서 $k_{1}k_{2}$는 L//G로 일정하다. 그러므로 우리는 L//G를 만드는 두 서로소 $k_{1}$과 $k_{2}$를 찾으면 된다. 여기서 $k_{1}$과 $k_{2}$는 1 이상의 자연..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
