분류 전체보기(77)
-
[BOJ 18578] Jimp Numbers
주어진 식을 다음과 같이 변형하자. 이때 $x>y$ 임에 주의하자. \[(x-y)^{2}+x^{2}+n=(x+y)^{2}\] \[n=x(4y-x)\] 여기서 $x|n$을 얻는다. 또 \[4|(\frac{n}{x}+x)=4y\] $x>y$조건에서 다음을 얻는다. \[y=\frac{\frac{n}{x}+x}{4}
2023.03.04 -
FFT(고속 푸리에 변환)
우리는 임의의 두 다항식을 좀 더 빠르게 곱하고 싶다. 각 $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_{..
2023.02.25 -
Funny fact in Linear Algebra
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..
2022.11.02 -
Lucy-Hedgehog Algorithm
이 알고리즘은 에라토스테네스의 체를 더 효율적으로 돌리기 위한 알고리즘으로 다음과 같은 점화식을 이용한다. \[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$이어야 한다. 이것은 소수이지만 이미 앞에서 걸렀다. 따라서..
2022.09.18 -
[BOJ 3904] The Teacher's Side of Math
이 문제는 서로 다른 두 소수 $p,q$에 대해서 $p^{1/n}+q^{1/m}(n,m\in \mathbb{N}_{\ge 1}$의 최소 다항식을 구하는 문제이다. 아래 두 개의 lemma를 증명하며 최소 다항식을 구하는 방법을 알아보자. $K$가 $F$의 field extension이라 하자. Lemma 1. $\forall \alpha \in K$, $\alpha$ acting by left-multiplication on $K$ is a $F$-linear transformation of $K$. Proof. 임의의 $x, y\in K$와 $a, b\in F$를 잡자. 그럼 $\alpha(ax+by)=\alpha ax+\alpha by = a(\alpha x)+b(\alpha y)$가 된다. 따라서 ..
2022.09.02 -
[BOJ 19549] 레이저 연구소
원점에서 $(n,m)$으로 레이저를 쏘는 상황을 생각해보자. 집은 몇 개가 부숴질까? $y=\frac{m}{n}x$를 생각해보자. 이 직선에서 $x,y$가 모두 정수인 점이 집이 있는 구간이다. 결국 $mx=ny$의 정수 해의 개수가 된다. $(m,n)=d$라 하면 $m'=m/d,\ n'=n/d$ 일 때 $m'x=n'y$이고 따라서 $x=\alpha n',\ y=\alpha m'(1\le \alpha \le d)$이다. 그러므로 총 $d$개 의 집이 부숴진다. 원점도 집이 있으므로 $d+1$개 부숴진다. 벽을 지난다는 것은 무엇을 의미할까? 세로 벽을 생각하면 위에서 생각한 직선이 $(a,b)$와 $(a,b+1)$의 사이를 지난다는 것을 의미한다 그렇다는 것은 $b
2022.08.21