엘릭시르제

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

한 줄 요약: $N \geq 3$부터 합성수다. $1$부터 $N$까지의 합은 간단하게 $S(N) = \frac{N(N+1)}{2}$로 나타낼 수 있다. 합성수는 소수와 소수의 곱 혹은 소수와 합성수의 곱 혹은 합성수와 합성수의 곱이다. 1. $N$이 $1$이라면 $S(1) = 1$이므로 이는 소수도 아니고 합성수도 아니다.2. $N$이 $2$라면 $S(2) = \frac{2 \times 3}{2} = 1 \times 3$이므로 소수다.3. $N$이 $3$보다 크거나 같다면 $S(N) = \frac{N(N+1)}{2}$에서 $N$은 $3$보다 크거나 같고 $N+1$도 $4$보다 크거나 같다. 이는 둘 중에 하나가 짝수여서 $2$로 나누어떨어진다고 가정했을 때, $N = 2$와 같이 $1$이 되지 않는다. ..

한 줄 요약: $N$이 제곱수이거나 제곱수를 $2$로 나눈 값이라면 양의 약수의 합은 홀수고 아니라면 짝수다.($16(4^{2})$, $72(\frac{12^2}{2})$, $\cdots$ 등은 홀수, $19$, $34$, $\cdots$ 등은 짝수) $N$이 주어졌을 때 양의 약수의 합이 무엇이냐고 한다면, 직접 약수를 구해서 합을 더해 줄 수 있다. 그리고 그 값이 홀수인지 짝수인지 판단 해볼수 있다. 그렇다고 이 방식이 컴퓨터로 계산했을 때 $10^{18}$ 스케일 정도까지는 폴라드 로 알고리즘을 사용한다면 엄청 느리거나 하지 않는다. 하지만 우리는 $N$을 이렇게도 나타낼 수도 있다. $N = p_{1}^{q_{1}} p_{2}^{q_{2}} \cdots p_{n}^{q_{n}} $ (단, $p_..