백준/수학 (35) 썸네일형 리스트형 [ICPC] 백준 28152 - Power of Divisors https://www.acmicpc.net/problem/28152힌트 1더보기문제에서 유효한 해가 존재할 때 $f(n)$의 값은 충분히 작다.힌트 2더보기$n^{f(n)} = x$라는 조건에 의해 $x$는 어떤 수의 거듭제곱으로 이루어져야만 함을 확인할 수 있다. 힌트 1과 힌트 2에서 언급한 사실을 종합했을 때, 후보를 빠르게 추릴 수 있는 방법이 있는가?풀이더보기$2^{64} > 10^{18}$이므로, $f(n)$이 가질 수 있는 최댓값을 64로 잡는다. 그러면 1부터 64까지 반복을 돌면서 $1 \leq i \leq 64$에 대해 어떤 정수 $a$가 $a^{i} = x$인지 $a$에 대해 이진탐색을 시행하여 확인할 수 있다. $a^{i} = x$를 만족하는 a를 찾을 경우, $f(a) = i$인지.. 백준 27437 - 분수찾기 2 https://www.acmicpc.net/problem/27437힌트더보기문제에 그려진 테이블을 유심히 보자. 위와 같이 구분한다고 했을 때 패턴을 찾아낼 수 있는가?풀이더보기위 힌트에서 주어진 테이블을 대각선으로 나눴다. 그러면 우리는 각 대각선에서 발견할 수 있는 중요한 성질을 다음과 같이 정리할 수 있다. 각 대각선에 속한 수들의 집합을 $D_{1}, D_{2}, D_{3}, ...$으로 부르며 원소의 갯수는 $1, 2, 3, ...$이다. 이때 $D_{i}$의 원소인 $\frac{y}{x}$에서 $MAX(x, y) = i$이다. 우리는 $\sum_{i = 1}^{n}\nolimits i \leq X$를 만족하는 $i$의 최댓값을 파라메트릭 서치로 찾아낼 수 있다. 그리고 대각선을 문제의 규칙에.. 백준 18287 - 체스판 이동 https://www.acmicpc.net/problem/18287 규칙 살펴보기 홀수 행와 짝수 행일 때의 이동은 그림으로 나타내면 다음과 같다. 문제에 아래로 가는 것만 가능하다 했으므로 다른 이동은 무시한다. 그러면 우리는 이 이동을 표현한 전이 행렬을 구상할 수 있다. MATRIX[i][j] := 현재 행의 i열에서 다음 행의 j열로 가는 경우의 수 그러면 $M^{2}$ 크기의 전이 행렬 두 개를 만들 수 있다. 이동 합성 행렬을 만든 건 좋은데 이 따로국밥인 행렬들을 어떻게 처리할지 난감하다. 이럴 때는 그냥 홀수 행 전이 행렬과 짝수 행 전이 행렬을 곱해 2번 이동하는 행렬을 만들면 된다. 그러면 우리는 2칸씩 이동하는 행렬을 표현했으므로 남은건 행렬 거듭제곱을 통해 이동 횟수 계산을 $O(M.. [ICPC] 백준 9341 - ZZ https://www.acmicpc.net/problem/9341 조건 정리 일단 문제를 편하게 풀기 위해 ZZ(0, 0)을 정의할 필요가 있다. $ZZ(0, 0) = b - a$로 둔다.(피보나치수열을 생각한다.) 직접 해보기 10 * 10 테이블을 단순한 dp로 출력해보자. 그러면 다음 발견을 할 수 있다. 어떤 항은 위처럼 Z 모양으로 더한 결과와 같다. 수식으로 나타내면 다음과 같다. $ZZ(a, b) = [\sum\limits_{i = 0}^{a}ZZ(i, b - 1)] + ZZ(0, b - 2)$ 그러면 우리는 위 식의 전개를 행렬로 표현할 수 있다. 예를 들어 c가 2인 경우 아래처럼 된다. $\left[ \begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\.. 백준 10986 - 나머지 합 https://www.acmicpc.net/problem/10986 힌트 더보기 $(A - B) \mod m = (A \mod m) - (B \mod m)$ 풀이 더보기 나머지의 성질에 대해 생각하면 $(A - B) \mod m = (A \mod m) - (B \mod m)$ 가 성립됨을 알 수 있을 것이다. 이를 문제에 적용하면 모듈러 값이 같다는 건 둘을 뺐을 때 0이 된다는 소리고 즉, pref[A] - pref[B]가 m으로 나누어진다는 것이 된다. 따라서 우리는 누적합을 계산하면서 각 나머지의 횟수를 세주고 $\binom{N}{2}$ 을 모두 계산해주면 된다. 참고로 나머지가 0인 경우는 이미 나누어진 것이므로 이거는 따로 더해주도록 한다. 물론 이항 계수의 계산에도 포함해야 한다. 전체 코드 .. 이전 1 2 3 4 5 ··· 7 다음
