45th Mongolian Mathematical Olympiad

Those $z_i$ are odd numbered $2n$th root of unity. In the figure regular $n$-gon. Consider following function's decomposition. $f(x)=(1+x)(1+x^2)\dots (1+x^n)$. Then $x^k$'s coefficient is a set whose sum of elements. We need to find $x^k$'s sum of coefficients, which is denoted by $A_n$. Here $n=2009$. Now consider that sum $f(\epsilon )+f({\epsilon }^2)+\dots +f({\epsilon }^n)$, here $\epsilon =\cos \frac{2\pi }{n}+i\sin \frac{2\pi }{n}$. We know that $\epsilon +{\epsilon }^2+\dots +{\epsilon }^n=0$ then we can easily see that ${\sum }_{k=1}^{n}f({\epsilon }^k)=n\cdot A_n$. Now compute the $f({\epsilon }^k)$, Assume $d=(k,n)$. Then $f({\epsilon }^d)=f({\epsilon }^k)$. Otherwise, numbers of all $d$ such that $d=(k,n)$ is $\phi \left(\frac{n}{d}\right)$. Also, $$f({\epsilon }^d)=(1+{\epsilon }^d{)}^d(1+{\epsilon }^{2d}{)}^d\dots (1+{\epsilon }^{n/d}{)}^d$$ and easy calculation, we get $$f({\epsilon }^d)={\left[(1+{\epsilon }^d)(1+{\epsilon }^{2d})\dots (1+{\epsilon }^{\frac{n}{d}\cdot d})\right]}^d$$ Because of $x^n-1={\prod }_{k=1}^n(x-{\epsilon }^k)$ then substituting $x=-1$, we get $(-1{)}^n-1=(-1{)}^{n}f(\epsilon )$, In other word $f(\epsilon )=1+(-1{)}^{n+1}$. Observe that $({\epsilon }^d{)}^{\frac{n}{d}}=1$, we get $f({\epsilon }^d)=(1+(-1{)}^{\frac{n}{d}+1}{)}^d$. Finally $$n\cdot A_n=\sum _{d|n}\phi \left(\frac{n}{d}\right)\cdot {\left(1+(-1{)}^{\frac{n}{d}+1}\right)}^d.$$