이 문제는 두 문제를 섞은 것이다. 그들은 각각 [BOJ 13716] 피보나치 수열처럼 보이지만... 과[BOJ 17372] 피보나치 수의 최대공약수의 합 이다. 이 문제를 도전하기 전에 위 두 문제를 해결하고 오자. 앞서 포스팅에서 [BOJ 17372]를 다루었다. 그때와 같은 방식으로 본 문제에서 주어진 식을 단순화 하면 $$\sum_{d=1}^{n}d^{k}F_{d}C(d)$$ 이며 $C(d)=2\sum_{i=1}^{n/d}\phi(i)-1$이다. [BOJ 17372]와 근본적인 방법은 똑같다. xudyh's sieve를 이용하여 $C(d)$를 빠르게 계산하고 $C(d)$에 $n/d$항이 존재한다는 특성을 이용해 $O(\sqrt{n})$만에 문제를 해결하는 것이다. 반면, 이를 위해서는 $\sum_{d..

우리는 이전 글에서 Lucy-Hedgehog algorithm(이하 Lucy)에 대해 배웠다. Lucy는 다음의 점화식을 이용한다. $\[S(v,p)=S(v,p-1)-(S(v/p,p-1)-S(p-1,p-1))\] 우리는 앞서 2개의 배열 A,B를 사용하여 목표 값인$S(N, sqrt(N))$을 계산하였다. 여기서 확인해야할 것은$S(v,p)$가 나타내는 값은 2부터$v$까지의 값 중$p$까지 에라토스테네스의 체를 돌렸을 때 걸러지지 않은 값들의 개수라는 것이다. 최적화를 위해서 우리는$\sqrt{N}\le yp$인 경우만 계산하면 된다. 우리가 계산해야할 것은$S(N/i, p)$이다. 따라서$i\le N/p^{2}$를 만족한다. 또한, 우리는$v> y$인 경우만을 고려하므로$i\le N/..

우리가 어떤 자연수 $n$이 주어져 있고 이 $n$이 $x^{2}+xy+y^{2}(x,y\in\mathbb{Z})$로 나타내질 수 있는지 알고싶다. 그러기 위해서는 먼저 어떤 소수 $p$가 $x^{2}+xy+y^{2}$인지 알아보자. Lemma 1. 소수 $p$에 대하여 $p=x^{2}+xy+y^{2}(x,y\in\mathbb{Z})$ iff $p\equiv 1\pmod{3}$거나 $p=3$이다. (pf) $(\Rightarrow)$ $x$가 3의 배수라고 가정하자. 만약 $3|y$이면 $p$가 소수라는 가정에 모순이다. 따라서 $3\nmid y$이고 $p\equiv 1\pmod{3}$이다. $x,y$가 3의 배수가 아니라고 가정하자. 그럼 $x,y$는 3으로 나눈 나머지가 $1,2$중 하나가 될 것이다..

구해야 하는 것은 $$\sum_{(a,b)}\sum_{(c,d)}\sum_{(e,f)}[ \gcd(Y_{a,b},Y_{c,d},Y_{e,f})=1]$$ 이다. 뫼비우스 역변환을 이용하면 $$\sum_{s=1}^{359999}\mu(s)\sum_{(a,b)}\sum_{(c,d)}\sum_{(e,f)}[s|Y_{a,b}][s|Y_{c,d}][s|Y_{e,f}]$$ 이다. 그럼 우리는 $Y_{a,b}$이 각각 어떤 값을 가지고 얼마나 많은 중복이 일어나는지 세면 답을 구할 수 있다. 문제에서 $Y_{a,b}=X_{a}\times X_{b}\pmod{359999}$이다. 즉, $X_{a}$들의 범위는 $0~359998$이라 생각해도 무방하다. 특히, $359999 = 599 \times 601$로 CRT를 이용..

문제를 접근하는 방법은 각 소수$q$에 대해서 $ax^{2}+bx+c \equiv 0\pmod{q}$를 만족하는 $x$를 찾는 것이다. 그럼 소수 $q$는 어느 범위까지 검사해야할까? 문제에서 구하라고 하는 것은 주어진 곱을 나누는 제곱수이다. 적절한 커팅을 이용해서 확인해 봐야 하는 소수의 개수를 줄이도록 하자. $(an^{2}+bn+c)^{1/3}$보다 작은 소수들을 모두 검사한다고 하자. 어떤 수 $x$가 어떤 자연수 $k$에 대해서 $ax^{2}+bx+c=p\cdot k$를 만족한다고 하자, 그럼 에라토스테네스의 체처럼 $(an^{2}+bn+c)^{1/3}$ 보다 작은 소수들로 각 $p(x)$들을 나누자. 남은 $p(x)$들은 $(an^{2}+bn+c)^{1/3}$보다 큰 소수 2개의 곱으로 이루..

굉장히 멋진 아이디어를 사용하는 문제!! 정말 멋진 문제!! 우리는 Dirichlet convolution을 modulo p에 대해서 계산한다는 것을 관찰하자. 이때 다음을 생각한다. Lemma. 모든 산술 함수 $f:\{1,\cdots,n\}\rightarrow \mathbb{Z}$에 대해서 $2^{p}>n$이면 $f^{p}\equiv \epsilon \pmod{p}$이다. Proof. 함수 $f^{p}$는 다음과 같다. $$f^{p}(n)=\sum_{a_{1}\cdots a_{p}=n}f(a_{1})\cdots f(a_{p})$$ 이때 summation 아래의 조건을 만족하는 튜플 $(a_{1},\cdots,a_{p})$를 고려하자. 하나의 튜플을 찾았다면 permutation을 통해 다른 튜플을 찾..