1. 문제 16563번: 어려운 소인수분해 (acmicpc.net) 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 500만 이내의 값에 대한 100만개의 수가 주어질때 각각을 소인수분해하는 문제 2. smallest prime factor smallest prime factor 알고리즘은 어떤 수의 가장 작은 소인수를 찾아 배열에 저장하는 알고리즘이다. 소인수분해를 수행하는 기본 알고리즘은.. p = 2부터 시작해서 $\sqrt{n}$까지 나눠보면서 소인수를 찾는데 #trivial prime factorizatio..
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..
1. 약수의 개수 자연수 n의 소인수분해가 $$n = p_{1}^{x_{1}}p_{2}^{x_{2}}...p_{k}^{x_{k}}$$라고 한다면, n의 양의 약수의 개수는 $$d(n) = (x_{1}+1)(x_{2}+1)...(x_{k}+1)$$ n을 소인수분해하여, 소인수들의 지수 + 1의 곱의 합이 약수의 개수이다. 1-1) 간단한 증명 왜냐하면 n의 약수는 $p_{1}, p_{2}, ... , p_{k}$들의 곱으로 이루어져 있는데, 각각은 $x_{1}, x_{2}, ... , x_{k}$개씩 사용할 수 있다. 따라서 곱의 법칙에 의해 모든 경우의 수는 $p_{1}, p_{2}, ... , p_{k}$을 각각 (0,1,2,...,$x_{1}$), (0,1,2,...,$x_{2}$), ... , (0..
1. 합동식에서 기본적으로 알아야하는 성질 1-1) 양변에 어떤 정수에 대한 덧셈이나 뺄셈을 하더라도 상관없다. $a \equiv b (mod p)$이고 $c \equiv d (mod p)$이면, $$a \pm c \equiv b \pm d (mod p)$$ 그러므로, c = d이면, 양변에 동일한 수를 더하거나 빼더라도 합동식은 변하지 않는다. $$a \pm c \equiv b \pm c (mod p)$$ 1-2) 양변에 어떤 정수에 대한 곱셈을 하더라도 상관없다 $a \equiv b (mod p)$이고 $c \equiv d (mod p)$이면, $$ac \equiv bd (mod p)$$ 그러므로, c=d이면, 양변에 동일한 수를 곱하더라도 합동식은 변하지 않는다. $$ac \equiv bc (mod..
1. 베주 항등식(Bézout's Identity) 적어도 하나가 0이 아닌 두 정수 a,b에 대하여 $$ax+by = gcd(a,b)$$를 만족하는 정수해 x,y가 반드시 존재한다. 여기서 정수해 x,y는 유일하지 않다. 왜냐하면, 양변에 ab를 더하고 빼보면 $$ax+ab + by-ab = gcd(a,b)$$이므로, $$a(x+b) + b(y-a) = gcd(a,b)$$이므로, (x,y)가 정수해라면, (x+b,y-a)도 정수해가 된다. 2. 유클리드 알고리즘(Euclidean algorithm) 최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법 (tistory.com) 최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법 1. 최대공약수 두 자연수 a,b가 공통으로 가지는 약수중에서 가장 큰..
1. 오일러의 phi 함수(Euler's phi function, totient function) $\varphi(n)$은 1부터 n까지의 자연수 중에서 n과 서로소인 자연수의 개수로 정의한다. 그 성질과 응용이 매우 다양하고 또 매우 어려운데... 하나하나 파고들면 끝도 없으니까 문제 풀면서 익히기로 하자 2. 구현 예시1 - 가장 간단한 구현 가장 간단한 방법은 1이상 n이하의 자연수 중에서, n과 서로소인 것의 개수를 세보면 된다. 그러니까 1이상 n이하의 자연수 중에서 n과 최대공약수가 1인 자연수의 개수가 n이하에서 몇개인지 세보면 된다. 유클리드 호제법을 이용해서 최대공약수를 구하는 함수를 만들고, def gcd(a,b): while b != 0: a,b = b,a%b return a 2부터 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
