$\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\N}{\mathbb{N}}$ $\newcommand{\gang}[1]{\langle #1 \rangle}$ We have to calculate the number of the possible value form of $x^{p}+q \pmod{n}$. Lemma 1. There exists a bijection between $\{x^{p}+q\pmod{n}\}$ and $\{x^{p}\pmod{n}\}$. Proof. For convenience, let each set be $A,B$ resp. Construct a map $\phi:A\rightarrow B$ with $\phi(\overline{a})=\overlin..

이 문제는 $\{1,\cdots,n\}$까지의 수 중에서 $\gcd(i,j)>1$을 만족하는 $(i,j)$ 쌍들을 최대한 많이 만들고 쌍을 만들 수 없는 경우 자기 자신이 쌍이 될 때 최소의 쌍의 개수가 몇 개인지 구하는 것이다. 우리는 $p>N/2$이면 $p$는 쌍을 만들 수 없다는 사실을 안다. 다음과 같은 과정을 생각해보자. $\{1\cdots n\}$에서 쌍이 완벽히 지어졌다 가정하자. 우리는 $n+1$을 저 집합에 추가하고 최적의 쌍을 얻어낼 것이다. 0. $n+1$이 소수이다. - $(n+1,n+1)$을 쌍으로 한다. 1. $\{1\cdots n\}$ 중에서 짝지어지지 않은 소수 $p$가 존재하여 $p|n+1$이다. - $(p,n+1)$을 쌍으로 한다. 2. $\{1\cdots n\}$에서 $..

주어진 식을 다음과 같이 변형하자. 이때 $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}

우리는 임의의 두 다항식을 좀 더 빠르게 곱하고 싶다. 각 $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$이어야 한다. 이것은 소수이지만 이미 앞에서 걸렀다. 따라서..