使用NTT需要保证模数mod 为质数。
通过以下代码求得一个模数的原根 ， 常见的质数的原根 998244353 -> 3 1e9+7 -> 5
#include#define ll long long#define IL inline#define RG registerusing namespace std;ll prm[1000],tot,N,root;ll Power(ll bs,ll js,ll MOD){ ll S = 1,T = bs; while(js){ if(js&1)S = S*T%MOD; T = T*T%MOD; js >>= 1; } return S;}IL ll GetRoot(RG ll n){ RG ll tmp = n - 1 , tot = 0; for(RG ll i = 2; i <= sqrt(tmp); i ++){ if(tmp%i==0){ prm[++tot] = i; while(tmp%i==0)tmp /= i; } } if(tmp != 1)prm[++tot] = tmp; //质因数分解 for(RG ll g = 2; g <= n-1; g ++){ bool flag = 1; for(RG int i = 1; i <= tot; i ++){ //检测是否符合条件 if(Power(g,(n-1)/prm[i],n) == 1) { flag = 0; break; } } if(flag)return g; }return 0; //无解 }int main(){ cin >> N; root = GetRoot(N); cout< <
g是mod(r * 2 ^ k + 1)的原根
| 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 |
| 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 |