본문 바로가기
728x90

백준브실골/정수론5

백준 27519, 소수의 합 개요 문제 링크 골드 2, 정수론, DP N을 서로 다른 소수의 합으로 표현하기 접근 DP에서는 knapsack에 가까우나 DP와 관련된 내용은 크지 않은 문제. 우선 100,000까지 체를 만들어야 하는 것은 쉽게 알 수 있다. 그리고 T가 10000번이니까 N=100,000까지 미리 값을 구해놓고 그 값을 T번 동안 출력만 해야 함을 알 수 있다. 그러면 미리 구해놓을 때는 어떻게 구하냐, 이렇게 생각하자. 중복되지 않은 경우를 생각하면 오름차순이고, 구성이 모두 달라야 한다. 그럼 우선 2의 합으로 만들어진 모든 경우를 만든다. 이때는 모든 짝수의 경우가 1일 것이다. 그리고 3, 5, 7이 포함된 경우를 고려한다. 이렇게 소수 크기대로 점차 큰 수가 포함된 경우의 수를 모두 더해주면 (소수개수 ×.. 2023. 2. 27.
백준 26092, 수학적인 최소 공통 조상 개요 문제 링크 골드 4, 정수론 두 정수를 가장 작은 소인수로 나눌 때 같아지는 지점 구하기 접근 LCA에 익숙한 사람은 최소공통조상이라는 말이 익숙했을 것이다. 딱히 관련은 없다. 가장 작은 소인수로 나눠가는데, 한 지점으로 같아지면, 그 이후부터는 소인수가 계속 같을 것이다. 또한 나누어준 소인수는 항상 오름차순이다. 두 수를 소인수분해를 하고 순서대로 정렬을 한다. 그리고 가장 긴 뒷꼬리의 곱을 구해주면 된다. N이 크니까 체를 만들고 코드를 짜주자. Pseudo code // 체 만들기 p = make_eras() vector fraction(a) { vector frac for (auto x:p) while (a%x == 0) a /= x, frac += x // 뒤집어서 앞에서부터 봐준다 r.. 2023. 2. 22.
백준 7806, GCD! 개요 문제 링크 골드 3, 정수론 N!과 K의 최대공약수 구하기 접근 N!을 구하는 것은 미친짓이고, N!안에 들어있는 소수의 개수를 모두 세는 것도 굳이 필요없다. 우리는 K의 소인수에 대해서만 필요하기 때문이다. 그러니 K를 먼저 소인수 분해하고, K의 소인수 p에 대해 K에서 p를 곱한 횟수와 N!에서 p를 곱한 횟수의 최솟값 만큼 p를 곱해주면 된다. N!에서 p를 곱한 횟수는 이렇게 세어준다. // n = 28, p = 3 // [인수, 곱횟수] [3,1], [6,1], [9,2], [12,1], [15,1], [18,2], [21,1], [24,1], [27,3] -> [3-27, 1] + [9-27, 1] + [27, 1] 3의 제곱수의 배수의 개수의 합을 구해준다. 3의 제곱수의 배수에 대.. 2023. 2. 22.
백준 16233, 수학 문제 개요 문제 링크 골드 1, 정수론 X-(X의 자리수합) = N이 되는 최소 X구하기 접근 분류가 수학으로 되어있는데 정수론에 가까운 것 같아 정수론으로 분류했다. 우선 기본적인 생각을 한 뒤 노가다를 돌려보자. 기본적인 생각이란? X는 N과 자리수 차이가 많이 나지 않는다. 왜냐? N의 자리수 합의 최댓값은 9가 9개 있는 999999999의 81이다. 최대로 81 쯤까지 더할 수 있는데, 자리수가 2이상 차이나면 N-X 가 81을 넘어버린다. 그러니 N*10까지 검사해보자. int sum(int x) while (x/=10) sum += x%10 return sum for (x = n~n*10) if (x-sum(x) == n) return x return -1 이렇게 1000이나 10000까지 돌려보.. 2023. 2. 19.
백준 20946, 합성인수분해 개요 문제 링크 골드 5, 정수론, 소수판정 자연수를 합성수의 곱으로 분해하기 접근 정수론은 실생활에는 큰 도움이 안되지만 코드포스에서 자주 다루는 주제이다. 이외에는 딱히 코테같은 곳에도 잘 안나온다. 합성수로 인수분해를 한다. 우선 2개의 소수를 짝을 지어줘야 한다. 그러니 만약 N이 소수라면 당연히 합성수 분해를 할 수 없다. 왜냐? 2개의 소수가 없기 때문. 사전순으로 우선하려면? 가장 작은 2개의 소수끼리 짝을 지어야 한다. 그런데 만약 소인수 분해 결과 소수의 개수가 홀수개라면? 즉 2개씩 짝을 지어서 하나가 남으면? 마지막에만 3개를 곱해주면 된다. 가장 먼저 출력될 놈이 가장 작아야 하니까 마지막에 큰 값을 출력할수록 이득이다. 이 부분에서 그리디를 끼운 것 같은데 그리디... 라고 하기에.. 2023. 2. 18.
728x90

티스토리툴바