Coding Test/Math

[14565] 역원(Inverse) 구하기 (확장 유클리드 호제법)

14565번: 역원(Inverse) 구하기 집합 Zn을 0부터 n-1까지의 정수 집합이라고 하자. Zn ∋ a, b, c 일 때, (a+b) mod n = 0이면 b는 a의 덧셈역이라고 하고 (a*c) mod n = 1이면 c는 a의 곱셈역이라고 한다. 정수 N, A가 주어졌을 때 Zn에서의 A의 www.acmicpc.net 분석 덧셈역 n-a (11 + 15) mod 26 = 0 곱셈역 xgcd(11﹡X, 26) = 1이 되는 X를 찾는 것 ➔ 11 * 𝒔 + 26 * 𝒕 = 1일 때 𝑆 값(곱셈역) (11 * 19) mod 26 = 1 확장 유클리드 알고리즘 확장 유클리드 호제법 유클리드 호제법 : 두 수의 최대 공약수 구하기 확장 유클리드 호제법 : 방정식의 해 구하기 베주 항등식 (Bezout's..

[21568] Ax+By=C (확장 유클리드 호제법)

21568번: Ax+By=C A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자. x, y는 정수 -1,000,000,000 ≤ x, y ≤ 1,000,000,000 www.acmicpc.net 분석 확장 유클리드 알고리즘 확장 유클리드 호제법 유클리드 호제법 : 두 수의 최대 공약수 구하기 확장 유클리드 호제법 : 방정식의 해 구하기 베주 항등식 (Bezout's Identity) 의 명제를 기반으로 해를 구하는 알고리즘 베주 항 karla.tistory.com 풀이 """ A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자. x, y는 정수 -1,000,000,000 ≤ x, y ..

확장 유클리드 알고리즘

확장 유클리드 호제법 유클리드 호제법 : 두 수의 최대 공약수 구하기 확장 유클리드 호제법 : 방정식의 해 구하기 베주 항등식 (Bezout's Identity) 의 명제를 기반으로 해를 구하는 알고리즘 베주 항등식 (Bezout's Identity) ax + by = d 를 만족하는 (x, y) 정수해는 d 의 값이 gcd(a, b) 의 배수일 때 존재하며, 이 존재하는 경우 나오는 값들만 (x, y) 의 정수해가 될 수 있다. 즉, d % gcd(a, b) == 0 인 경우이다. 만약 4x + 3y = 2 이라는 방적식이 있다고 하자. 이 때 (x, y)의 정수해는 ... ,(-1, 2), (2, -2), (5, -6), ... 등이 된다. 4, 3 의 최대공약수는 1이며 우변의 2는 1의 배수이기 ..

[10934] 최소공배수 (유클리드 호제법)

1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 분석 최소공배수 = A * B / 최대공약수 풀이 """ 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오. 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000) """ def gcd(a,b): if b==0: return a else: return gcd(b,a%b) T=int(input()) ..

[1850] 최대공약수 (유클리드 호제법)

1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 유클리드 호제법 두 수의 최대 공약수를 구하는 알고리즘 큰 수를 작은 수로 나누는 MOD 연산을 수행한다. 앞 단계에서 작은 수와 MOD 연산 결과값(나머지)으로 MOD 연산을 수행한다. 단계 2를 반복하다가 나머지가 0이되는 순간의 작은 수를 최대 공약수로 선택한다. 풀이 """ 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가..

[1033] 칵테일 (최소공배수, 최대공약수, 유클리드호제법)

1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 분석 사이클이 없는 트리 구조이므로 임의의 노드에서 DFS를 진행하면서 해결 DFS 과정에서 유클리드 호제법을 사용해 비율들의 최소공배수와 최대공약수를 구하고, 재료의 최소 질량을 구하는데 사용 풀이 """ 칵테일에 들어가는 재료 N개는 공개되어 있다. 총 재료 쌍 N-1개의 비율이 입력으로 주어진다. 칵테일을 만드는데 필요한 각 재료의 양 이때, 필요한 재료의 질량을 모두 더한 값이 최소가 되어야 한다. a b p q : a번 재료의 질량을 b번 재료의 질량으..

[11689] GCD(n, k) = 1 (오일러 피, 서로소)

11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 분석 구하고자 하는 오일러 피의 범위만큼 리스트를 자기 자신의 인덱스 값으로 초기화 2부터 시작해 현재 리스트의 값과 인덱스의 값이 같으면(소수) 현재 선택된 숫자k의 배수에 해당하는 수를 리스트에 끝까지 탐색하며 P[i]=P[i]-P[i]/k 연산을 수행 (i는 k의 배수) 리스트의 끝까지 2를 반복하여 오일러 피 함수 완성 풀이 """ 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 첫째 줄에 자연수 n (1 ≤ n ≤ 1012..

[1016] 제곱 ㄴㄴ 수(제곱으로 나누어떨어지지 않는 수)

1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 분석 min ≤ max ≤ min + 1,000,000 : 일반적인 반복문으로 구하면 시간초과 범위 A~B사이 pow(정수 제곱수)로 떨어지는 수 구함 ➔ checkList[ (A/제곱수 ~ B/제곱수)*제곱수-A]=True Fase 개수 출력 1. 제곱수인 4 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 j=1 : (4*1)-1=3 (3번 인덱스 제곱수 True) j=2 : (4*2)-1=7 (7번 인덱스 제곱수 T..

[1747] 소수&팰린드롬

1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 풀이 """ 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오. """ import math n=int(input()) # 에라토스테네스 체 소수구하기 a=[0]*1000..

[1456] 거의 소수 (에라토스테네스의 체)

1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 분석 에라토스테네스의 체를 이용해 빠르게 소수를 먼저 구함 주어진 소수들의 N제곱값이 A~B 범위안에 존재하는지 판별하며 갯수 체크 풀이 """ 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력 1 ≤ A ≤ B ≤ 10^14 5324 894739 183 """ import math min,max=map(int, input().split()) a..