K의 배수 Extreme

https://www.acmicpc.net/problem/31544 문제는 다음과 같다.

 

다음 문제를 하나의 생성함수로 나타내면 다음과 같다.

$\begin{align} f(x)&=(\prod_{i=1}^{N} (1+x^i))^M \\&=a_0+a_1x^1+a_2x^2+a_3x^3+\cdots \end{align}$

 

우리는 여기서 $\sum_{i=1}^{\infty} a_{Ki}$을 구해야 한다.

이를 구하기 위해서 a root of unity를 사용할 것이다.

 

$\zeta^K=1$인 a root of unity를 사용해보자.

$\zeta^K=1$은 $\zeta^K-1=0$으로 바꾼 후 인수분해할 수 있다.

 

$\zeta^K-1=(\zeta-1)(\zeta^{K-1}+\zeta^{K-2}+\cdots+\zeta+1)=0$

여기서 우리는 $\zeta^{K-1}+\zeta^{K-2}+\cdots+\zeta+1=0$을 유도할 수 있다.

 

그 후 $f(x)$에 $1, \zeta, \zeta^2, \cdots, \zeta^{K-1}$을 넣어보자.

 

$f(1)=2^{NM}=a_0+a_1+a_2+a_3+a_4+\cdots$

$f(\zeta)=(\prod_{i=1}^{N} (1+\zeta^i))^M=a_0+a_1\cdot\zeta+a_2\cdot\zeta^2+a_3\cdot\zeta^3+a_4\cdot\zeta^4+\cdots$

$f(\zeta^2)=(\prod_{i=1}^N (1+\zeta^{2i}))^M=a_0+a_1\cdot\zeta^2+a_2\cdot\zeta^4+a_3\cdot\zeta^6+a_4\cdot\zeta^8+\cdots$

$f(\zeta^3)=(\prod_{i=1}^N (1+\zeta^{3i}))^M=a_0+a_1\cdot\zeta^3+a_2\cdot\zeta^6+a_3\cdot\zeta^9+a_4\cdot\zeta^{12}+\cdots$

$\cdots$

$f(\zeta^{K-1})=(\prod_{i=1}^N (1+\zeta^{(K-1)i}))^M=a_0+a_1\cdot\zeta^{K-1}+a_2\cdot\zeta^{2K-2}+a_3\cdot\zeta^{3K-3}+a_4\cdot\zeta^{4K-4}+\cdots$

 

이를 다 더하면

$\begin{align} \sum_{i=0}^{K-1} f(\zeta^i)&=2^{NM}+\sum_{i=1}^{K-1} \prod_{j=1}^N (1+\zeta^{ij}) \\&=a_0 \end{align}$