엘릭시르제

문제 링크: https://www.acmicpc.net/problem/14317문제 풀이정수론, 포함 배제의 원리, 분할 정복을 이용한 거듭제곱 $N \leq 10^{18}$인 $i$, $j$가 있을 때 $(i^{A} + j^{B}) \pmod K = 0$와 $i \neq j$를 만족하는 순서 쌍 ($i$, $j$)의 개수를 구하는 문제이다. 굳이 위에 $10^{18}$을 언급하는 이유는 나이브한 $O(N^{2})$ 풀이는 쳐다도 볼 수가 없다는 뜻이다. 여기서 주목해야 하는건 $K$의 범위다. $10^{5}$보다 작거나 같으므로 이를 이용해보자. 먼저, '$N$보다 작거나 같은 $i$가 $K$로 나누었을 때 나머지가 $r$인 값은 총 몇 개 있는가?' 라는 해답부터 생각하면 된다. 당연하겠지만 $0 \..

문제 링크: https://www.acmicpc.net/problem/19124문제 풀이정수론 설명은 정말 간단한 문제. ${}_{n}C_{k} \bmod 2^{32}$를 구하면 된다.$2^{32}$는 매우 큰 수이기도 하고, 합성수여서 뤼카 정리를 사용하기에도 빡세보인다. 먼저 가장 쉬운 판별을 해보자.${}_{n}C_{k} = 2^E \cdot U$로 나타낼 때 $E \geq 32$이면 나누어떨어지므로 $U$를 계산할 필요가 없어진다. 이 $E$를 구하는 방법이라면 Legendre's formula를 이용해도 좋고 어렵지 않다. 다만 $p = 2$의 경우에는 $\nu_{2}(n!) = n - s_2(n)$($n$을 이진수로 나타내었을 때 $1$의 개수)로도 나타낼 수 있으니, $\nu_{2}({}_{..

문제 링크: https://www.acmicpc.net/problem/29537문제 풀이오일러 피 함수, 유클리드 호제법, 정수론 지문에서 간단하게 $\sum\limits_{d|n}{\sum\limits_{i = 1}^n{\mathrm{gcd}(d, i)}}$만 구하면 된다고 적혀져있다. 하지만 $n$은 $10^{12}$이므로 나이브하게 돌아가진 않을거니 식 정리를 해야한다. 먼저 시그마를 바꿔치기 해보자. $$ \sum_{i=1}^{n} \left( \sum_{d \mid n} \gcd(d, i) \right) $$이제 $\sum_{d \mid n} \gcd(d, i)$를 잘 변환하면 된다.우리는 약수 $d$를 고정하고 계산하는게 아니라 $i$를 고정하고 약수 $d$를 바꿔가며 푸는 것으로 바뀐다.그러..

문제 링크: https://www.acmicpc.net/problem/8483문제 풀이유리 등차수열의 내림 합, 정수론 $Ax + By > C$를 만족하는 위치에 모든 마천루가 사라졌다는 것은 $ Ax + By ≤ C$를 만족하는 위치에는 마천루가 남아있다는 뜻이다. 그리고 $x ≥ 0$, $y ≥ 0$인 정수 ($x$, $y$) 쌍의 마천루의 개수를 묻는 문제이다. 일단 $y$에 대해 식을 정리하면 $y \leq \frac{C-Ax}{B}$이고, 정수 값이어야 하니 $y$의 범위는 $0$부터 $\lfloor \frac{C-Ax}{B} \rfloor$까지. 즉 $\lfloor \frac{C-Ax}{B} \rfloor + 1$개다. $x$도 마찬가지로 $y$가 $0$ 이상의 값을 가지려면, $C - Ax ..