1181: [STT2024WCR1] 快速傅里叶变换

快速傅里叶变换（$\mathcal{FFT}$）是一种用于计算序列的离散傅里叶变换（$\mathcal{DFT}$）或其逆（$\mathcal{IDFT}$）的算法。它是一种高度优化的计算技术，特别适合于处理长度的数据序列。$\mathcal{FFT}$ 通过将 $\mathcal{DFT}$ 矩阵分解为稀疏（大多数元素为零）因子的乘积来加速计算过程。这种方法可以将计算 $\mathcal{DFT}$ 所需的时间从数据量的平方级降低到线性级别，具体来说，复杂度可以从 $\mathcal{O(n^2)}$ 减少到 $\mathcal{O(n \log_2 n)}$，其中 $n$ 是数据的大小。

快速傅里叶变换的应用范围非常广泛，包括但不限于工程、音乐、科学和数学等领域。它在人工智能计算中也扮演着重要角色，特别是在深度学习中，快速傅里叶变换作为一种基础计算方式，用于降低计算复杂度和提升计算速度。

历史发展方面，快速傅里叶变换的概念可以追溯到 1965 年，当时由 J.W.库利 和 T.W.图基 首次提出。尽管早期的算法已经存在，但现代通用的快速傅里叶变换算法是在 1965 年提出的。此外，高斯在 1805 年提出了类似于现代快速傅里叶变换的思想，但没有进行详细的计算复杂度分析。



你是 $\texttt{Chat FFT}$，一款由 $\texttt{CloseAI}$ 自主研发的只会回答有关 $\mathcal{FFT}$ 问题的人工智能。

具体地说，现有 $n$ 规模的数据等待 $\mathcal{FFT}$ 处理，你需要输出传统算法 $\mathcal{DFT}$ 与 $\mathcal{FFT}$ 计算相同量级数据所用时间的比值。

这里我们认为 $\mathcal{FFT}$ 的时间复杂度是 $\mathcal{O(n \lfloor \log_2 n \rfloor)}$ 的，其中 $\lfloor c \rfloor$ 表示对 $c$ 向下取整，例如 $\lfloor 1.2 \rfloor = 1$，$\lfloor 3.0 \rfloor = 3$。对于 $0$ 和 $1$ 规模的数据，两种算法都不用计算。

输入的第一行一个正整数 $T$，表示数据组数。

接下来 $T$ 行，第 $i+1$ 行包含一个整数 $n_i$，表示数据规模。

对于每组数据输出一行，表示 $\mathcal{DFT}$ 与 $\mathcal{FFT}$ 计算该相同量级数据所用时间的比值，化为最简分数。

6
4
8
2
0
1
1000000000

2
8/3
2
0
0
1000000000/29