우리는 이전 글에서 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$중 하나가 될 것이다..

우리는 임의의 두 다항식을 좀 더 빠르게 곱하고 싶다. 각 $n-1$차 다항식을 $A(z), B(z)$라고 하자. 또 $C(z):=A(z)B(z)$라고 하자. FFT의 핵심 아이디어는 Lagrange Interpolation이다. Lemma. (Lagrange Interpolation) 임의의 $m-1$차 다항식(in field)은 $m$개의 서로 다른 점으로 유일하게 결정된다. Proof. 임의의 $m-1$차 다항식을 $f(x):=a_{m-1}x^{m-1}+a_{m-2}x^{m-2}+\cdots+a_{1}x+a_{0}$라고 두자. 이 때 우리가 서로 다른 $m$개의 점 $\{b_{i}\}$들에 대하여 그 함숫값들 $\{f(b_{i})\}$를 알고 있다고 가정하자. 그럼 임의의 $i$에 대해서 \[a_{..

A funny fact came from this problem. Consider the two ordered basis of $M_{n}(F)$ which are \[\alpha=\{E_{11},E_{12},\cdots,E_{1n},\cdots,E_{n1},\cdots,E_{nn}\}\] \[\beta=\{E_{11},E_{21},\cdots,E_{n1},\cdots,E_{1n},\cdots,E_{nn}\}\] We have $[L_{B}]=[L_{B}(E_{11})\ L_{B}(E_{12})\ \cdots\ L_{B}(E_{nn})]$. Consider $BE_{ij}$. We have ${\rm col}_{j}(BE_{ij})=Be_{i}={\rm col}_{i}(B)$. Thus, first co..

이 알고리즘은 에라토스테네스의 체를 더 효율적으로 돌리기 위한 알고리즘으로 다음과 같은 점화식을 이용한다. \[dp[v][m]=dp[v][m-1]-(dp[\lfloor\frac{v}{m}\rfloor][m-1]-dp[m-1][m-1])\] 여기서 $dp[v][m]$은 $m$까지의 수로 체를 돌렸을 때 1부터 $v$까지 수 중 소수로 간주되는 것이 몇 개인지 말하고 있다. 우리가 $m-1$까지의 수를 보았다고 하자. 만약 $m$이 소수가 아니라면 체를 돌릴 필요가 없으니 $dp[v][m]=dp[v][m-1]$이다. 또 $m^{2}$이 $v$보다 크다면 역시 체를 돌릴 필요가 없어 $dp[v][m]=dp[v][m-1]$이다. 그럼 $m^{2}m-1$이어야 한다. 이것은 소수이지만 이미 앞에서 걸렀다. 따라서..

이라는 제목의 논문(?)을 써보았다. 내 블로그에 있는 증명에 있는 오류를 모두 수정하여 썼다~ 한참 전에 썼었는데 까먹고 못 올리고 있었다ㅎㅎ 블로그에 신경쓸 수 없을 정도로 바빴다. 물론 지금도 바쁘고! 윌슨의 정리 확장을 이용한 재미있는 알고리즘을 소개했으니 한 번 읽어보기를 바란다!