본문 바로가기
728x90

정수론13

[python] 백준 1033 칵테일 https://www.acmicpc.net/problem/1033 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 문제 해결 최소공배수를 이용해서 상대가격 비교 두 수(p,q)의 최소 공배수는 p*q//gcd(p,q) 이다. 상대 가격을 구한다음(P(2) =$\frac{P(1)}{i[1]} \times i[2] $) (i[1], i[2]는 1과 2의 상대 가격 비율) 모든 수의 최대공약수로 나누어서 출력한다. CODE n = int(input()) A = [[] for _ in range(n)] visited.. 2023. 2. 24.
[python] 백준 11689 GCD(n, k) = 1 https://www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 n의 약수 중 소수인 것을 $p_{1}, p_{2}, ... p_{a}$ 라 할 때 소수의 개수는 다음과 같이 구할 수 있다. $\phi$ (n) = n $\times \prod_{i=1}^{a} (1-\frac{1}{p_{i}})$ 시간초과가 나지 않게 리스트를 사용하지 않고 for문을 돌면서 소수를 찾으면 ans -= ans/p 를 한 다음 n에서 소수 p의 흔적을 없앤다. p를 약수로 갖지 않을 때 까지 계속 나눠준다는 것이다... 2023. 2. 24.
[python] 백준 1747 소수&팰린드롬 https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 문제 해결 n이상의 소수에서 찾는 것이므로 리스트의 원소 개수를 1,000,000(n의 최댓값)보다 커야한다. ($\times$ 10 함) 소수는 에라토스테네스체로 걸러낸다. CODE import sys input = sys.stdin.readline import math n = int(input()) A = [0]*(10000001) for i in rang.. 2023. 2. 23.
[python] 백준 1456 거의 소수 https://www.acmicpc.net/problem/1456 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 문제 해결 편하게 0부터 끝 수(b)까지 리스트 만들어 놓고 하면 메모리 초과가 걸린다. 따라서 int(sqrt(b))+1 개의 리스트 공간을 만들어 놓고 소수인 인덱스를 제곱, 세제곱 하면서 a와 b 사이에 들어오는지를 확인해야 할 것이다. CODE import math import sys input = sys.stdin.readline a, b = map(int, input().split()) A = [.. 2023. 2. 23.
728x90