D - Zeta Sum Editorial
by 
karinohito
まず、二項定理から、
\[\text{(与式)}=\sum_{k=0}^{N}\binom{N}{k}\left\{\left(\sum_{a=1}^{N}\sum_{i=0}^{a-1}\zeta_a^{ik}\right)\left(\sum_{b=1}^{N}\sum_{j=0}^{b-1}\zeta_b^{j(N-k)}\right)\right\}\]
が成り立ちます。ここで、
\[\sum_{i=0}^{a-1}\zeta_{a}^{ik}=\begin{cases} 0&(a\nmid k) \\ a&(a\mid k) \end{cases}\]
が成り立ちます。
証明
\(\zeta_{a}^{i(k+a)}=\zeta_{a}^{ik}\) であるので, \(0\le k\lt a\) の時を考えればよいです。
\(0<k<a\) の時
\(\gcd(a,k)=g\), \(a=a'g\), \(k=k'g\) とすれば、
\(\zeta_{a}^{ik}=\zeta_{a'}^{ik'}\) 及び, \(\zeta_{a'}^{(i+a')k'}=\zeta_{a'}^{ik'}\) から
\[\sum_{i=0}^{a-1}\zeta_{a}^{ik}=g\sum_{i=0}^{a'-1}\zeta_{a'}^{ik'}\]
を得ます。
よって、\(\gcd(a,k)=1\) の場合が示されればよいです。
以下 \(a,k\) は互いに素とします。
\(i=0,1,\dots,a-1\) について、 \(ki\mod{a}\) は全て異なります。
実際、 \(ki\equiv ki'\mod{a}\) とすると、 \(k(i-i')\equiv 0\mod{a}\) より、\(i=i'\) となります。
従って、
\[\sum_{i=0}^{a-1}\zeta_{a}^{ik}=\sum_{i=0}^{a-1}\zeta_{a}^{i}=0\]
となります。 ただし、最後の等号には \(\zeta_{a}^{0},\zeta_{a}^{1},\dots,\zeta_{a}^{a-1}\) が \(x^a-1\) の相異なる根である事及び解と係数の関係を用いています。
\(k=0\) の時
\(\zeta_{a}^{ik}=1\) であるので、等式が成り立ちます。
よって、
\[\sum_{a=1}^{N}\sum_{i=0}^{a-1}\zeta_a^{ik}=\sum_{a\mid k}a=d(k)\]
となります。 ただし、\(d(k)\) は
\[d(k)=\begin{cases} \frac{N(N+1)}{2}&(k=0)\\ k\text{の正の約数の総和}&(k\neq 0) \end{cases}\]
で定められる値です。
同様にして、
\[\sum_{b=1}^{N}\sum_{j=0}^{b-1}\zeta_b^{j(N-k)}=d(N-k)\]
であるので、
\[\text{(与式)}=\sum_{k=0}^{N}\binom{N}{k}d(k)d(N-k)\]
となります。 \(d(k)\) の値や二項係数の値は全体を \(O(N\log N)\) で計算することができるのでこの問題を解くことができました。
posted:
last update: