최대공약수의 약수는 모든 수들의 공약수이고 최소공배수의 배수는 모든 수들의 배수이다

1. 문제 1565번: 수학 (acmicpc.net) 1565번: 수학 배열 D와, 배열 M이 주어졌을 때, D에 있는 모든 수의 배수이며, M에 있는 모든 수의 약수인 수의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 수들의 최소공배수의 배수는, 모든 수들의 공배수이며, 수들의 최대공약수의 약수는, 모든 수들의 공약수이다. M에서 최대공약수를 구한 다음에, 최대공약수의 약수들을 구한다. $O(\sqrt{N})$으로 구할 수 있다. 여기서 set()을 이용해서 중복을 피해준다 다음 D에서 최소공배수를 구해준다. a,b의 최소공배수는 a*b/gcd(a,b)로 구할 수 있 그리고 M에서 구한 약수들이 최소공배수의 배수인지 판단해준다 from sys import stdin de..

• format_list_bulleted 정수론
• · 2023. 5. 28.
• textsms

베주의 항등식 - 최대공약수로 만들 수 있는 정수

1. 문제 25333번: 개구리 (acmicpc.net) 25333번: 개구리 Albert는 개구리 장난감을 이용한 놀이를 즐겨한다. 이 장난감은 우측으로 $A$cm 혹은 좌측으로 $B$cm 점프할 수 있다. 예를 들어 현재 개구리 장난감의 위치가 $0$이고 $A = 4$, $B = 2$ 라 하자. 아래 그 www.acmicpc.net 2. 풀이 예제를 보면 A,B의 최대공약수의 배수의 개수가 정답일 것 같은데 조금 수학적으로 생각해보면 A,B로 만들 수 있는 자연수가 X 이내에 몇개나 있느냐?라는 문제와 같은데 오른쪽으로 x번 A만큼 점프하면 Ax가 되고 왼쪽으로 y번 B만큼 점프하면 By가 되니까, 만들 수 있는 정수는 Ax+By형태와 같다. 이는 베주의 항등식 형태와 같으며, "정수 x,y에 대하여..

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

피보나치 수열 심화과정4 -피보나치 수의 최대공약수 놀라운 성질-

1. 피보나치 수의 최대공약수 다음과 같이 정의되는 피보나치 수열 $F_{0} = 0, F_{1} = 1$이고 $F_{n+2} = F_{n+1} + F_{n}, n \geq 0$ 에 대하여, n번째 피보나치 수 $F_{n}$와 m번째 피보나치 수 $F_{m}$의 최대공약수 $gcd(F_{n}, F_{m})$은 n,m의 최대공약수 gcd(n,m)번째 피보나치 수와 같다. $$gcd(F_{n}, F_{m}) = F_{gcd(n,m)}$$ 2. 보조정리1 임의의 정수 k에 대하여, $gcd(a,b) = gcd(a+kb, b)$ 증명) x가 a,b의 공약수라면, a는 x로 나누어 떨어지고 ($x | a$로 표시) b도 x로 나누어 떨어진다. 그러므로, 임의의 정수 k에 대하여 kb도 x로 나누어 떨어진다. a도..

• format_list_bulleted 정수론
• · 2023. 5. 26.
• textsms

세 수의 최소 공배수를 최대로 만드는 방법

1. 문제 25342번: 최대 최소공배수 (acmicpc.net) 25342번: 최대 최소공배수 $N = 3$인 경우, $1, 2, 3$을 선택하면 최소공배수는 $6$이다. $N = 4$인 경우, $2, 3, 4$를 선택하면 최소공배수는 $12$이다. www.acmicpc.net 2. 풀이 3개의 수의 최소공배수가 최대가 될려면 어떻게 해야할까 두 수 a,b의 최소공배수는? a = Gn이고 b = Gm으로 표현할 수 있다면(G는 a,b의 최대공약수, n,m이 서로소) a,b의 최소공배수는 L = Gnm이다. 이 최소공배수가 가장 클려면 어떻게 해야할까? L = Gnm이므로, L = am이거나 L = bn으로 표현할 수 있다. 이 둘은 모두 ab보다 작거나 같다. 따라서, L

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

어떤 수를 서로소 쌍의 곱으로 빠르게 분해하는 방법

1. 문제 2436번: 공약수 (acmicpc.net) 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 2. 풀이 최대공약수 G, 최소공배수 L이 주어질때 두 수 x,y는 어떻게 구할까 $$x = Gk_{1}$$ $$y = Gk_{2}$$ 이 때 L은 다음과 같이 구할 수 있다 $$L = Gk_{1}k_{2}$$ 따라서 $k_{1}k_{2}$는 L//G로 일정하다. 그러므로 우리는 L//G를 만드는 두 서로소 $k_{1}$과 $k_{2}$를 찾으면 된다. 여기서 $k_{1}$과 $k_{2}$는 1 이상의 자연..

• format_list_bulleted 정수론
• · 2023. 3. 8.
• textsms

두 수의 최대공약수와 두 수의 합은 무슨 관계가 있을까

1. 문제 25375번: 아주 간단한 문제 (acmicpc.net) 25375번: 아주 간단한 문제 양의 정수 $a$, $b$가 주어지면, $gcd(x, y) = a$이고 $x + y = b$인 자연수 쌍 $(x, y)$가 존재하는지의 여부를 출력하자. www.acmicpc.net 2. 풀이 gcd(x,y) = a라는 것은 x,y가 a의 배수라는 것이다. ( a >= 1) 즉 x,y는 어떤 자연수 $k_{1}$와 $k_{2}$에 대하여 $$x = ak_{1}$$ $$y = ak_{2}$$ 그러므로 x+y = b를 a로 나눈다면.. $$k_{1} + k_{2} = \frac{b}{a}$$ 여기서 $k_{1}$와 $k_{2}$이 자연수이므로 우변 $\frac{b}{a}$는 자연수이다. 그러므로 자연수 쌍 (..

• format_list_bulleted 정수론
• · 2023. 3. 8.
• textsms