등차수열 구간의 최대공약수를 한번에 구하는 방법

1. 문제 23888번: 등차수열과 쿼리 (acmicpc.net) 23888번: 등차수열과 쿼리 등차수열은 연속하는 두 항의 차이가 일정한 수열을 뜻한다. 연속한 두 항 중 뒷항에서 앞항을 뺀 값을 공차라고 한다. 초항이 $a$이고 공차가 $d$인 등차수열이 주어진다. 수열의 $i$번째 원소를 www.acmicpc.net 2. 풀이 L번째 항부터 R번째 항까지의 합과 최대공약수를 구하는 문제 등차수열의 합은 초항이 $a_{1}$이고 항 수가 n개이며 공차가 d일때.. $$\frac{n(a_{1} + a_{n})}{2}$$ 등차수열의 일반항은 a + (n-1)d이다. 그러면 L번째 항부터 R번째 항까지의 합은.. 초항이 a + (L-1)d이고 끝 항은 a + (R-1)d이며.. 항 수는 R-L+1개이니까...

• format_list_bulleted 정수론
• · 2023. 2. 27.
• textsms

중국인의 나머지 정리(Chinese Remainder Theorem) 기본 이해하기

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..

• format_list_bulleted 정수론
• · 2022. 12. 30.
• textsms

모듈로 연산에서 나눗셈을 하는 방법(모듈로 곱셈의 역원 구하기)

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..

• format_list_bulleted 정수론
• · 2022. 12. 16.
• textsms

확장된 유클리드 알고리즘(extended euclidean algorithm) 구현해보면서 익히기

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가 공통으로 가지는 약수중에서 가장 큰..

• format_list_bulleted 정수론
• · 2022. 12. 16.
• textsms

최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법

1. 최대공약수 두 자연수 a,b가 공통으로 가지는 약수중에서 가장 큰 약수를 최대공약수라고 부른다. 중요한 성질중 하나는 최대공약수의 약수는 a,b의 공약수이다. 2. 유클리드 호제법 두 양의 정수 a,b (a>b)에 대하여 a = bq + r ( r은 0이상 b 미만)이라고 하면, a,b의 최대공약수는 b,r의 최대공약수와 같다. 즉, gcd(a,b) = gcd(b,r)이다. 만약 r=0이라하면, a,b의 최대공약수는 b이다. 3. 유클리드 호제법 활용 단 1번만 사용해서는 그 진짜 힘을 알 수 없다. a = bq + r이면 a,b의 최대공약수는 b,r의 최대공약수와 같다 b를 r로 나눠서 b = rq2 + r2라는 식을 얻는다면, 결국 b,r의 최대공약수는 r,r2의 최대공약수와 같다. 여기서 r을..

• format_list_bulleted 정수론
• · 2022. 8. 10.
• textsms