FFT用到的各种素数

是这样的,这几天在写 FFT,由于是在模意义下的,需要各种素数……

然后就打了个表方便以后查了、

如果 r \cdot 2^k + 1 是个素数,那么在\bmod r \cdot 2^k + 1意义下,可以处理 2^k 以内规模的数据,

2281701377=17\cdot 2^{27}+1 是一个挺好的数,平方刚好不会爆 long long

1004535809=479\cdot 2^{21}+1 加起来刚好不会爆 int 也不错

还有就是 998244353=119 \cdot 2^{23}+1

下面是刚刚打出来的表格(g\bmod (r \cdot 2^k + 1)的原根)

(more…)

Read More