1. 연분수 표현에서 a,b의 최대공약수를 바로 구하는 방법 $\frac{A}{B}$의 연분수 표현을 구하고자 한다면, A/B가 기약분수 형태로 들어가줘야한다. 기약분수로 바꿀려면 A,B의 최대공약수가 g = gcd(A,B)일때, $p_{k} = A/g, q_{k} = B/g$이고 그래서 $\frac{A}{B} = \frac{p_{k}}{q_{k}}$이다. 따라서, A/B가 기약분수가 아닐때, 연분수 표현 p,q를 구한 다음 A를 p[-1]로 나눠주면 A,B의 최대공약수가 된다. #A/B가 기약분수가 아닐때, A,B의 최대공약수 구하기 def continued_fraction(p,q): f = [] while q != 0: f.append(p//q) p,q = q,p%q return f def conve..
1. 문제1 7516번: 알렉산드리아의 디오판토스 (acmicpc.net) 7516번: 알렉산드리아의 디오판토스 알렉산드리아의 디오판토스는 알렉산드리아에 살던 이집트 수학자이다. 그는 정수로된 해 만을 가지는 다항 방정을 처음으로 연구한 수학자이다. 그를 기리기 위해서 후대에 이 방정식은 디오 www.acmicpc.net 2. 풀이 주어진 방정식 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$을 정리하면, $$\frac{y+x}{xy} = \frac{1}{n}$$이다. 그래서 $$n(y+x) = xy$$를 얻는다. 솔직히 여기서 넘어가기 어려운데, (억지라는 생각이 들 정도..) $n^{2} = pq$라 하자. p,q는 정수이다. 즉, p,q는 $n^{2}$의 약수이다. 그리고..
1. 중국인의 나머지 정리(Chinese Remainder Theorem) 정수 $m_{1}, m_{2}, ..., m_{n}$이 임의의 i,j = 1,2,...,n에 대하여 $i \neq j$일때, $m_{i}$와 $m_{j}$가 서로소라면, 즉 $$gcd(m_{i}, m_{j}) = 1, i \neq j$$라고 하자. 일차연립합동식 $$x \equiv a_{1} (mod m_{1})$$, $$x \equiv a_{2} (mod m_{2})$$, $$x \equiv a_{3} (mod m_{3})$$, $$\vdots$$, $$x \equiv a_{n} (mod m_{n})$$ 의 해는 mod $m_{1}, m_{2}, ..., m_{n}$에 대하여 유일하게 존재한다. 2. 보조정리 1 정수 a,b,k..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
