Bluestein's Algorithm 用于当不是 \(2\) 的整数次幂时对多项式的 (I)DFT。
考虑现在要求：
\[f_m = \sum\limits_{k = 0}^{n - 1} a_k w^{mk} \]Bluestein 的核心思想在于拆 \(mk\)。不难证明 \(mk = \frac{m(m - 1)}{2} + \frac{k(k + 1)}{2} - \frac{(m - k)(m - k - 1)}{2}\)。那么：
\[f_m = w^{\frac{m(m - 1)}{2}} = \sum\limits_{k = 0}^{n - 1} (a_k w^{\frac{k(k + 1)}{2}}) w^{-\frac{(m - k)(m - k - 1)}{2}} \]这样我们把这个东西化成了卷积形式。但是发现 \(m - k\) 可能是负数，所以需要把另外一个多项式平移 \(n\) 位再做卷积。
时间复杂度是 \(O((n + m) \log n)\)。
注意到我们没有用到 \(w\) 是模意义下的单位根的特性，所以这里 \(w\) 其实可以取任意整数，所以 Bluestein's Algorithm 其实就是代入一个等比数列，然后多点求值。
注意有些博客说的 \(mk = \frac{1}{2} (m^2 + k^2 - (m - k)^2)\) 有局限性，因为 \(w\) 可能没有二次剩余。
1. P6800 【模板】Chirp Z-Transform
模板。
标签：frac,Algorithm,limits,sum,mk,Bluestein From： https://www.cnblogs.com/zltzlt-blog/p/18162648