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)的原根)

r \cdot 2^k + 1 r k g
3 1 1 2
5 1 2 2
17 1 4 3
97 3 5 5
193 3 6 5
257 1 8 3
7681 15 9 17
12289 3 12 11
40961 5 13 3
65537 1 16 3
786433 3 18 10
5767169 11 19 3
7340033 7 20 3
23068673 11 21 3
104857601 25 22 3
167772161 5 25 3
469762049 7 26 3
998244353 119 23 3
1004535809 479 21 3
2013265921 15 27 31
2281701377 17 27 3
3221225473 3 30 5
75161927681 35 31 3
77309411329 9 33 7
206158430209 3 36 22
2061584302081 15 37 7
2748779069441 5 39 3
6597069766657 3 41 5
39582418599937 9 42 5
79164837199873 9 43 5
263882790666241 15 44 7
1231453023109121 35 45 3
1337006139375617 19 46 3
3799912185593857 27 47 5
4222124650659841 15 48 19
7881299347898369 7 50 6
31525197391593473 7 52 3
180143985094819841 5 55 6
1945555039024054273 27 56 5
4179340454199820289 29 57 3

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2014/07/fft-prime-table

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

6 thoughts on “FFT用到的各种素数

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.