8422205.html

NTT中可用素数模数原根表

常用素数：
P = 1004535809  ====>  pr = 3
P = 998244353  =====>  pr = 3

//（g 是mod(r*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
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

另外，不在本表中的数可以用以下程序求解

#include<cstdio>
#define LL long long
using namespace std;
const int maxn = 1e6 + 5;
int mod, phi;
int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}
int main() {
    scanf("%d", &mod), phi = mod - 1;
    for(register int i = 2, p = 1; i <= mod; ++i, p = 1) {
    	if(gcd(i, mod) != 1) continue;
    	for(register int a = i; a != 1; (a *= i) %= mod, ++p) ;
    	if(p == phi) {printf("%d\n", i);return 0;}
    }
    return 0;
}

---------------------------------upd/2018/12/19/-------------------------------------------

我们有更科学的判原根的方法：

http://blog.leanote.com/post/rockdu/0330

Rockdu's Blog

本文转载自https://www.cnblogs.com/Guess2/p/8422205.html

NTT中可用素数模数原根表

另外，不在本表中的数可以用以下程序求解

---------------------------------upd/2018/12/19/-------------------------------------------

我们有更科学的判原根的方法：

导航

最近发表

大佬们的友链