PS를 위한 정수론 - (2) 유클리드, 확장 유클리드 호제법
[목차] 1. 유클리드 호제법 2. 확장 유클리드 호제법 3. 모듈러(modular) 연산에서의 곱셈의 역원 4. 예시 문제 1. 유클리드 호제법 유클리드 호제법은 정수론을 조금이라도 공부했다면, 혹은 공부하지 않았더라도 충분히 들어봤을 것이다. 유클리드 호제법은 자연수 $a$, $b$ 가 주어졌을 때, $gcd(a, b)$ 즉, $a$와 $b$의 최대 공약수를 구하는 방법이다. $a$를 $b$로 나눈 몫을 $q$라고 하고, 나머지를 $r$이라고 하면 $a = bq + r$ 로 나타난다. 이때, $gcd(a, b) = gcd(b, r)$을 만족한다. 이유는 $gcd(a, b) = g$라고 하면, $g|a$, $g|b$ 를 만족하게 되고, $r = a - bq$이므로 $g|(a - bq) = r$ 을 만족..
[BOJ 17353] 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별
[문제] www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net [난이도] - Platinum II (solved.ac 20.12.22 기준) [필요 개념] - Lazy Propagation with Segment Tree - Fenwick Tree 디스크립션은 간단하다. 두 종류의 쿼리가 들어오고, 한 쿼리는 구간 [L, R]에 순서대로 1, 2, ..., R-L+1을 더해준다. 나머지 한 쿼리는 X번째 원소의 값을 출력해준..