본문 바로가기

분할 정복을 이용한 거듭제곱/정수 거듭제곱

 (44)
백준 18151번: DivModulo https://www.acmicpc.net/problem/18151 18151번: DivModulo Modulo (mod) is a very common operator on integers. For two integers n and d with d > 0, r ≡ (n mod d) is defined where 0 ≤ r < d and there exists an integer q, such that n = q × d+r. For example, (200 mod 5) ≡ 0 means that the remainder of 200 divi www.acmicpc.net 정수론에 대한 지식이 부족한 저로서는 매우 힘든 문제 중 하나였습니다. 처음에는 Lucas' Theorem과, Andrew Granvil..
백준 10909번: Quaternion inverse https://www.acmicpc.net/problem/10909 10909번: Quaternion inverse 각 \(A\)가 주어질 때마다, \(AB = 1\)을 만족하는 \(B = a + bi + cj + dk\)들 중 하나를 나타내는 네 개의 정수 \(a\), \(b\), \(c\), \(d\)를 공백으로 구분하여 \(T\) 줄에 걸쳐 출력하면 된다. 만약 이런 \(B\)가 www.acmicpc.net 사원수, quaternion이라는 낯선 대상이 주어졌을 뿐, 실제로는 복소수의 역원을 구하는 것과 크게 다르지 않습니다. 일반적인 사원수에 대해 역수를 구하는 방법은 다음 링크 와 같이 주어집니다. 다시 말하면, 다음 식이 성립합니다. $$ \times < a-bi-c..
백준 27299번: 헌내기 현철 https://www.acmicpc.net/problem/27299 27299번: 헌내기 현철 불과 몇 달 전만 해도 새내기였던 현철이는 $22$학번을 이십이학번이 아닌 이이학번으로 읽는다는 것을 신기하게 생각했다. 그런데, 이제 $23$학번이 들어온다는 소식에 현철이는 큰 충격에 빠졌 www.acmicpc.net 구해야 하는 값은 $A^{B^{C}}$를 $10^{7}$으로 나눈 나머지입니다. 여기까지는 생각하기 매우 쉽지만, $C$의 범위가 매우 큽니다. Euler's Theorem을 반복하여 적용할 수 있지만, 저는 그냥 한 번만 적용하고 끝내는 게 더 편할 수도 있다는 생각을 했습니다. 왜냐하면 17315번 에서 이미 한 번 구현했기 때문입니다 ㅎㅎ.. 주의할 점은 엣지 케이스인데, $$A^{B^{..
백준 14679번: 영우와 '갓4' https://www.acmicpc.net/problem/14679 14679번: 영우와 ‘갓4’ 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 몬스터의 수 N이 주어진다. (1 ≤ N ≤ 50,000,000) 두 번째 줄에는 영우가 키우는 캐릭터의 공격력(A), 방어력(D), 최대 체력(H)이 차례대로 www.acmicpc.net $N$이 매우 크지만, 풀이는 생각보다 단순한 문제입니다. 우선 가장 나이브하게 $O(N(A_{p}+D_{p}+H_{p}))$ 또는 $O(N\log(A_{p}D_{p}H_{p}))$으로 매번 몬스터의 공격력, 방어력, 체력을 시뮬레이션하는 것은 시간제한을 통과할 수 없어보입니다. 그런데 어차피 $A_{k} \; D_{k} \; H_{k}$는 각각 1부터 100, ..
백준 9556번: 수학 숙제 https://www.acmicpc.net/problem/9556 9556번: 수학 숙제 각 테스트 케이스마다 조건을 만족하는 N자리 정수의 개수를 1,000,000,007로 나눈 값을 출력한다. www.acmicpc.net 처음엔 포함 배제로 풀려고 했다가, 제가 포함 배제에 익숙하지 못해서 구현을 포기하고 다른 방법으로 풀게 됐습니다. 이 문제의 첫 번째 포인트는 $N$자리 수는 한 개 이상의 0으로 시작할 수 있다는 것입니다. 즉 우리가 체크해야 할 수의 범위는 0부터 $10^{N}-1$까지입니다. 두 번째 포인트는 이 문제의 나눠 떨어진다는 표현은 나머지가 0이라는 것입니다. 그래서 0은 모든 양의 정수로 나누어 떨어지는 수라고 합니다. 이 문제는 물론 포함 배제로도 풀 수 있겠지만, 더 쉬운 관..
백준 16201번: 발코니 공사 https://www.acmicpc.net/problem/16201 16201번: 발코니 공사 첫째 줄에 별장 발코니의 크기 R, C와 부서지지 않은 칸의 개수 K가 주어진다. (1 ≤ R ≤ 1,000,000,000, 2 ≤ C ≤ 1,000,000,000, 0 ≤ K ≤ 1,000) 둘째 줄부터 K개의 줄에는 부서지지 않은 칸의 위치가 공백 www.acmicpc.net 도미노의 모양새에 대한 조건이 너무 강력해서 티어가 낮아진 문제입니다. 이 문제는 colorless한 $1 \times 2$ 도미노의 타일링을 다루고 있고 특별한 조건으로 "가로로만 놓을 수 있음"이 있습니다. 또 하나의 조건은 도미노를 최대한 많이 써야만 한다는 것입니다. 그래서 각 row에 대해 총 몇 개의 도미노를 놓을 수 있는지..
백준 26132번: Fair Division https://www.acmicpc.net/problem/26132 26132번: Fair Division After sailing the Seven Seas and raiding many ships, Cap’n Red and his crew of fellow pirates are finally ready to divide their loot. According to ancient traditions, the crew stands in a circle ordered by a strict pirate hierarchy. Cap’n Red starts by www.acmicpc.net 비록 해당 대회에서 제일 약한 급의 문제이긴 하지만 ICPC World Finals 2021 문제입니다! 풀이는 약간의 수학..
백준 16214: N과 M https://www.acmicpc.net/problem/16214 16214번: N과 M 임의의 자연수 N과 M이 주어져 있다. A^B를 A의 B승이라고 할 때, 수열 N, N^N, N^(N^N), N^(N^(N^N)), ... 의 수들을 M으로 나눈 나머지는 수열의 어느 지점부터 항상 일정한 값을 가진다. N과 M이 주어져 있 www.acmicpc.net 일반적인 power tower 유형에서 모든 지수에 $N$을 넣어준 것이므로 난이도가 어떤 면에선 더 쉬워졌다고 볼 수 있습니다. 본문은 매우 훌륭한 자료인 https://rkm0959.tistory.com/181 을 인용했습니다. 위 글에 따르면 다음이 성립합니다. (Notation은 위 링크를 참조해주시기 바랍니다.) $$ [N,N,N, \cdo..

티스토리툴바