특정한 조건을 만족하는 정수를 찾는 방법 - 이분 탐색 제대로 활용하기

1. 문제1 https://atcoder.jp/contests/abc341/tasks/abc341_d D - Only one of two AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 n,m,k가 주어지는데 n이나 m중 어느 하나만으로 나누어 떨어지는 정수들을 오름차순 정렬할때, k번째로 작은 양의 정수를 찾는 문제 예를 들어 n = 2, m = 3, k = 5이면 2,3,4,8,9,10,...은 각각 2나 3중 어느 하나만으로 나누어 떨어지는 정수들이다. 4는 2로 나누어 떨어지지만 3으로 나누어 떨어지지 ..

• format_list_bulleted 이분 탐색
• · 2024. 2. 21.
• textsms

자연수를 더해서 최소공배수를 최소로 만들기

1. 문제 11414번: LCM (acmicpc.net) 11414번: LCM 두 자연수 A, B가 주어졌을 때, A + N과 B + N의 최소공배수가 최소가 되는 자연수 N을 구하시오. www.acmicpc.net 2. 풀이 임의의 정수 k에 대하여 $$gcd(a,b) = gcd(a+kb,b)$$ 를 이용하자. 그러면, $$gcd(a+n, b+n) = gcd(a-b, b+n) = gcd(a+n, b-a)$$ 를 얻는다. 그래서 a < b이면, $a+n \leq gcd(a+n,b+n) \leq b-a$ 최대공약수로 gcd(a+n,b+n) = gcd(a-b,b+n) = gcd(b-a,b+n) = b-a라고 한다면... (gcd(a,b) = gcd(abs(a),abs(b))이기 때문) b+n이 b-a의 배수라는..

• format_list_bulleted 정수론
• · 2023. 6. 17.
• textsms

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

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부터 n까지의 최소공배수를 빠르게 구하는 방법

1. 문제 11690번: LCM(1, 2, ..., n) (acmicpc.net) 11690번: LCM(1, 2, ..., n) 첫째 줄에 1보다 크거나 같고, n보다 작거나 같은 모든 자연수의 최소공배수를 출력한다. 정답이 매우 커질 수 있기 때문에, 232로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 두 수 a,b의 최소공배수를 어떻게 구하는지 생각해본다면.. a랑 b를 소인수분해하고... 각각 소인수분해에서.. 소인수의 지수가 큰것끼리 곱하면 그것이 a,b의 최소공배수이다. 예를 들어 18과 24의 최소공배수를 구한다면.. $$18 = 2 * 3^{2}$$ $$24 = 2^{3} * 3$$ 여기서 소인수는 2와 3만 나타나는데.. 각각에서 지수가 큰 경우는 $2^{3}$이랑 $..

• format_list_bulleted 정수론
• · 2023. 5. 4.
• 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