原根

这个的用处还是非常大的

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

定义

，且 。则称 是 的一个原根。

是否有原根

只有 ，其中 为奇素数 ， 为正整数。

计算最小原根

这里直接使用最常见的作法。由小到大枚举 。 。那么只需要判断 就可以了，如果有一个为 ，则这个数不是 的一个原根。根据一些玄学引论， 的最小原根是 级别的，所以即使 很大，这个的时间复杂度仍然可以接受。

证明

考虑反证，令 而且 。且 。根据欧拉定理 。所以我们可以解一组二元一次方程，根据裴蜀定理 。所以 。所以必定满足至少一组 。这与上文相违背，所以得证。

代码

#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;
    }
}