原根

这个的用处还是非常大的

在模意义下的乘法可以通过原根转换为加法。
NTT 需要原根。

定义

$\gcd(g,m) =1$ ，且 $\text{ord}_{m}g = \varphi (m)$ 。则称 $g$ 是 $m$ 的一个原根。

是否有原根

只有 $m=2,4,p^a,2p^a$ ，其中 $p$ 为奇素数， $a$ 为正整数。

计算最小原根

这里直接使用最常见的作法。由小到大枚举 $g$ 。 $\varphi(m) =p_1^{a_1}p_2^{a_2}..p_k^{a_k}$ 。那么只需要判断 $g^{\frac{\varphi(m)}{p_i}}\equiv 1 \bmod m$ 就可以了，如果有一个为 $1$ ，则这个数不是 $m$ 的一个原根。根据一些玄学引论， $m$ 的最小原根是 $m^{0.25}$ 级别的，所以即使 $m$ 很大，这个的时间复杂度仍然可以接受。

证明

考虑反证，令 $t<\varphi(m)$ 而且 $g^t \equiv 1$ 。且 $g^{\frac{\varphi(m)}{p_i}}\not\equiv 1 \bmod m$ 。根据欧拉定理 $g^{\varphi(m)}\equiv 1$ 。所以我们可以解一组二元一次方程，根据裴蜀定理 $kt-a\varphi(m) =\gcd(t,\varphi(m))$ 。所以 $g^{\gcd(t,\varphi(m)) + a\varphi(m)}\equiv g^{\gcd(t,\varphi(m))}\equiv1\bmod m$ 。所以必定满足至少一组 $\gcd(t,\varphi(m))\mid \frac{\varphi(m)}{p_i}$ 。这与上文相违背，所以得证。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 10101010;
int a[50],n;
int varphi(int x) {
    int ans = x;
    for(int i = 2;i * i <= x;i++) {
        if(x % i) continue;
        ans = ans / i * (i - 1) ;
        while((x % i) == 0) x = x / i;
    }
    if(x > 1) ans = ans / x * (x - 1) ;
    return ans;
}
int qpow(int a,int b,int mod) {
    int x = 1;
    for(;b;b>>=1,a = 1LL * a * a % mod) {
        if(b & 1) x = 1LL * a * x % mod;
    }
    return x;
}
int p[N],vis[N];
void solve(int limit) {
    for(int i = 2;i <= limit;i++) {
        if(!vis[i]) p[++p[0]] = i;
        for(int j = 1;j <= p[0] && p[j] * i <= limit;j++) {
            vis[i * p[j]] = 1;
            if((i % p[j]) == 0) break;
        }
    }
}
int main() {
    solve(1e7);
    int T = read();
    while(T--) {
        memset(a,0,sizeof(a));
        n = read();
        int phi = varphi(n);
        int m = phi,ans = 0;
        for(int i = 1;i <= p[0] && p[i] * p[i] <= phi;i++) {
            if(phi % p[i]) continue;
            a[++a[0]] = p[i];
            while((phi % p[i]) == 0) phi = phi / p[i];
        }
        if(phi > 1) a[++a[0]] = phi;
        for(int i = 1;i <= m;i++) {
            int check = 0;
            for(int j = 1;j <= a[0];j++) {
                if(qpow(i,m/a[j],n) == 1) check = 1;
            }
            if(check == 0) {
                ans = i;break;
            }
        }
        cout << ans << endl;
    }
}