1. 문제 15712번: 등비수열 (acmicpc.net) 15712번: 등비수열 첫째 줄에 a, r, n, mod가 공백으로 구분되어 주어진다. a, r, n, mod는 모두 1보다 크거나 같고, 109보다 작거나 같은 자연수이다. www.acmicpc.net 초항이 a, 공비가 r, 항 수가 n인 등비수열의 합을 mod로 나눈 나머지를 구하는 간단한 문제 초항이 a이고 공비가 r이며 항 수가 n인 등비수열의 합은.. 공비 r이 1이 아니면, $$S = a \times \frac{r^{n}-1}{r-1}$$ 이라는 아주 쉬운 공식이 있고 이거에 따라 계산해서 mod로 나눈 나머지 구하면 되는거 아니냐 라고 쉽게 생각하면 이 문제는 풀수가 없다 a,r,n이 작으면 상관 없겠지만... 매우 크면 $r^{n..
1. 오일러의 정리(Euler's theorem) a와 n이 서로소인 양의 정수이면, 다음이 성립한다 $$a^{\varphi(n)} \equiv 1 (mod n)$$ 여기서 $\varphi(n)$은 n에 대한 오일러 phi 함수이다. 서로소가 아니라면 다음과 같이 쓸 수 있다. $$a^{\varphi(n) + 1} \equiv a (mod n)$$ n이 소수 p이면, $\varphi(p) = p-1$이므로, a,p가 서로소이면 $a^{p-1} \equiv 1 (mod p)$이다. 페르마의 소정리는 오일러의 정리의 특수한 케이스이다. 2. 거듭제곱을 어떤 정수로 나눈 나머지 $a^{n}$을 어떤 정수 p로 나눈 나머지는 어떻게 구할 수 있을까? $a^{n}$을 직접 계산한 다음에, p로 나눈 나머지를 구하..
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. 문제 14245번: XOR (acmicpc.net) 14245번: XOR 첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다. 두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다. 세 번째 줄 www.acmicpc.net 구간에 어떤 수를 XOR하는 쿼리와 어떤 index에 대응하는 원소를 출력하는 쿼리를 수행하는 문제 2. 풀이 구간에 수를 연산하니까 느리게 갱신되는 세그먼트 트리가 필요할 것 같고 index 하나 원소만 출력하는 트리는 이미 배웠으니까 def create_segment(A,tree,tree_index,A_start,A_end): if A_start == A_end: tree[..
1. 페르마의 소정리(Fermat's little Theorem) 1-1) p가 소수이고, a가 p의 배수가 아니면( = a와 p가 서로소이면 = gcd(a,p) = 1)이면, $$a^{p-1} \equiv 1 (mod p)$$이다. 1-2) p가 소수이면, 모든 정수 a에 대하여 $$a^{p} \equiv a (mod p)$$ 응용하는 방법은 여러가지가 있겠지만, 하나하나 다 나열할 수도 없고, 접한지 얼마 안되었으니 나도 다 모르고 증명도 굳이 할 필요없을 것 같고, 받아들이면서 문제를 풀면서 익혀보기로 하자 2. 응용 - 합성수 판정 페르마의 소정리 역은 성립하지 않는다. 즉, a와 p가 서로소일때, $$a^{p-1} \equiv 1 (mod p)$$가 성립한다면, p는 소수이다는 거짓이다. 즉, ..
1. 문제 11653번: 소인수분해 (acmicpc.net) 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 2. 소인수분해 하는 방법? 어렵게 생각할 필요 없이 사람이 소인수 분해를 어떻게 하는지 생각해보자. 100을 소인수분해 한다고 해보자. 암산으로 5*20 >>> 5*4*5 >> 5^2 * 2^2이 나오기는 하는데... 이게 어떻게 이루어지는가??? 처음부터 생각해보자. 소인수분해는 소수들의 곱이다. 그러니까 소수의 최솟값인 2부터 시작해서 주어진 수 100을 나눠보면 된다. 만약에 100이 2로 나누어진다면? 100 = 2 * 50이다. 그러면.. 우리는 어떤 걸 이제 나누어보는가? 100을 2로 나누고 나온 몫인 50을..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
