엘릭시르제

문제 링크: 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 ..

문제 링크: https://www.acmicpc.net/problem/28383문제 풀이소인수분해, 정수론 네 제곱수의 합의 가짓수를 구하는 방법은 Jacobi's four-square theorem를 이용하면 된다.간략하게 설명하면 $r_4(n)$이 $n$의 네 제곱수의 합의 가짓수를 구하는 함수인데,$n$이 홀수라면 $8\sigma(n)$를 구하면 되고, $n$이 짝수라면 $ n = 2^{k}m$으로 나타낼 때, $24\sigma(m)$을 구하면 된다.당연하겠지만 $\sigma(n)$를 구하기 위해서 소인수분해가 들어간다. $n = p_1^{q_1}p_2^{q_2}p_3^{q_3}\cdots p_k^{q_k}$으로 나타내면 $\prod_{i=1}^k \frac{p_i^{q_i + 1} - 1}{p_i..

이게 무슨 의미냐면, 먼저 $1$부터 $N$까지의 합부터 생각해보자. $\sum\limits_{i=1}^{n} i$는 간단하게 $\frac{n(n+1)}{2}$로 쓸 수 있다. 그러면 이 값에 다시 시그마를 붙이면? $\sum\limits_{i=1}^{n} \frac{i(i+1)}{2}$이 된다. 이 값은 무엇일까? 일단은 그냥 식 정리를 해보자. $\frac{1}{2} \sum\limits_{i=1}^{n} (i^{2}+i)$로 바꿔 쓸 수 있고,  $ \sum\limits_{i=1}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6} $이므로 $\frac{1}{2} (\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2})$가 된다.$\frac{n(n+1)(2n+1)}{..