给定在平面上的点 (1,0), (2,0), .... (n,0) 上发现的一组 n 个粒子电荷载流子。 在 (i,0) 点发现的粒子电荷记为 Qi。作用在粒子上的力由以下公式给出：
C is a Coulomb's constant.
给出一个算法来计算 Fi，对于总复杂度为 O(nlgn) 的所有粒子。 提示：使用FFT算法。
看起来 Fi 已经分为偶数点和奇数点了..
我想过将每个总和相除来计算 FFT（但除以什么..？） 然后总是对一半的点求和（因为这就是 FFT 的原因），然后减去公式中给出的总和的结果。
知道如何做得更好吗？
看起来像家庭作业，因此没有提供适合您的案例的实际代码，而是提供一些示例和提示。
for FFT类算法：
将数据集大小设置为2通过零填充
所以除以两半很简单（没有余数）
创建递归函数来计算类似 FFT 的东西
其中对数据集重新排序，将其分成两半并递归调用 self 两次（每次使用不同的一半数据）并添加 if 语句以开始。如果数据集size<=1 or 2然后直接返回计算值以确保递归停止。
在这两个递归调用之后，将数据重新排序并将它们组合成结果
如果需要，从结果中删除零填充
例如我的就是这样NTT看起来像（数论变换）
//---------------------------------------------------------------------------
void fourier_NTT:: NTT_fast(DWORD *dst,DWORD *src,DWORD n,DWORD w)
{
// recursion stop condition if the data is single number ...
if (n<=1) { if (n==1) dst[0]=src[0]; return; }
DWORD i,j,a0,a1,n2=n>>1,w2=modmul(w,w);
// reorder even,odd to dst array
for (i=0,j=0;i<n2;i++,j+=2) dst[i]=src[j];
for ( j=1;i<n ;i++,j+=2) dst[i]=src[j];
// recursion
NTT_fast(src ,dst ,n2,w2); // even
NTT_fast(src+n2,dst+n2,n2,w2); // odd
// restore results
for (w2=1,i=0,j=n2;i<n2;i++,j++,w2=modmul(w2,w))
{
a0=src[i];
a1=modmul(src[j],w2);
dst[i]=modadd(a0,a1);
dst[j]=modsub(a0,a1);
}
}
//---------------------------------------------------------------------------
完整的源代码和更多信息是here https://stackoverflow.com/q/18577076/2521214.
始终将快速实施结果与慢速实施结果进行比较！
随着数据集大小的增加，某些系数或索引中的小错误可能会导致结果出现巨大差异。
上面的实现速度很慢NTT功能：
//---------------------------------------------------------------------------
void fourier_NTT:: NTT_slow(DWORD *dst,DWORD *src,DWORD n,DWORD w)
{
DWORD i,j,wj,wi,a,n2=n>>1;
for (wj=1,j=0;j<n;j++)
{
a=0;
for (wi=1,i=0;i<n;i++)
{
a=modadd(a,modmul(wi,src[i]));
wi=modmul(wi,wj);
}
dst[j]=a;
wj=modmul(wj,w);
}
}
//---------------------------------------------------------------------------
[Notes]
现在你有了分离方程
导出直接计算的值和通过 2x 半递归调用计算的值之间的系数差，并相应地恢复结果，以便输出与正确的结果匹配。