NTT用到的各种素数

lolifamily

转载自 miskcoo

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

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

如果 $𝑟 (2 𝑘 + 1)$ 是个素数，那么在 $m o d 𝑟 (2 𝑘 + 1)$ 意义下，可以处理 $2 𝑘$ 以内规模的数据。

$2281701377 = 17 \times 227 + 1$ 是一个挺好的数，平方刚好不会爆 long long。

$1004535809 = 479 \times 221 + 1$ 加起来刚好不会爆 int 也不错。

还有就是 UOJ 常用的 $998244353 = 119 \times 223 + 1$ 。

打表方法：对于每个 $𝑘$ ，找到最小 $𝑟$ 满足 $𝑟 (2 𝑘 + 1)$ 是素数（ $𝑔$ 是 $m o d 𝑟 (2 𝑘 + 1)$ 的原根）。

$𝑟 (2 𝑘 + 1)$	$𝑟$	$𝑘$	$𝑔$
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