素数原根表

是这样的，这几天在写 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)$的原根）

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
1998585857	953	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