hdu 4992 Primitive Roots
百度百科有关于 Primitive Root的解释判断数是否有原根：模n有原根的充要条件是n = 1,2,4,p,2p,p^q，其中p是奇质数，q是任意正整数。所以预先判断数n是否有原根，然后用欧拉公式求出n的m=φ(n)从2~n-1遍历找出n的最小原根a：
判断a^m % n==1 是否成立计算出所有m的因子（1和m除外）y，若a^y % n==1，则a不可能是n的原根。因为存在性质：如果正整数gcd(a,m) = 1，正整数 d 满足a^d≡1(mod m)，则 d 整除 φ(m)。得到所有a^x % n {2<=x<m，gcd(x,m)==1}的值为n的原根，证明：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef __int64 LL; const int MAXN = 1005; int prim[MAXN], nprm; bool vis[MAXN]; int n, m; void init_prim() { for (int i = 2; i< MAXN; ++i) { if (!vis[i]) prim[nprm++] = i; for (int j = 0; j< nprm && prim[j]&i < MAXN; ++i) { vis[prim[j]*i] = 1; if (i % prim[j] == 0) break; } } } int Euler(int x) { int res = x; for (int i = 0, k; i< nprm ; ++i) { k = prim[i]; if (k * k > x) break; if (x % k == 0) { res = res/k*(k-1); while (x%k==0) x/=k; } } if (x!=1) res = res/x*(x-1); return res; } int nfen, fen[100][2]; void m_divide(int x) { nfen = 0; for (int i = 0, k; i< nprm ; ++i) { k = prim[i]; if (k * k > x) break; if (x % k == 0) { fen[nfen][0] = k; fen[nfen][1] = 0; while (x%k==0) x/=k, ++fen[nfen][1]; ++nfen; } } if (x!=1) fen[nfen][0]=x, fen[nfen++][1]=1; } LL mpow(LL a, int b, LL mod) { LL res = 1LL; while (b) { if (b&1) res = res*a%mod; a = a*a%mod; b >>= 1; } return res; } int caonima = 0; LL ri; void dfs(int idx, LL all) { if (caonima) return; if (idx == nfen) { if (all == 1LL || all == m) return; if (mpow(ri, all, n) == 1LL) caonima = 1; return; } for (int i = 0; i<=fen[idx][1]; ++i) { dfs(idx+1, all); all *= fen[idx][0]; } } int check(LL r) { LL res = r; if (mpow(r, m, n) != 1LL) return 0; caonima = 0; ri = res; dfs(0, 1); if (caonima) return 0; return 1; } int gcd(int a, int b) { return b==0?a:gcd(b,a%b); } int opt[1000000], cnt; void solve() { m = Euler(n); m_divide(m); int ff = 0; for (int i = 2; i< n; ++i) { if (check(i)) { ff = i; break; } } if (!ff) { printf("-1\n"); return; } cnt = 0; opt[cnt++] = ff; LL res = ff; res = res*ff%n; for (int i = 2; i< m; ++i, res = res*ff%n) { if (gcd(i, m) == 1) { opt[cnt++] = res; } } sort(opt, opt+cnt); printf("%d", opt[0]); for (int i = 1; i< cnt; ++i) { printf(" %d", opt[i]); } puts(""); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGE init_prim(); while (scanf("%d", &n) != EOF) { if (n==2) puts("1"); else if (n==4) puts("3"); else { int p = n, cc = 0; if (n%2==0) n>>=1; for (int i = 0, k; i<nprm ; ++i) { k = prim[i]; if (k*k > n) break; if (n % k == 0) { if (++cc > 1) break; while (n % k==0) n /= k; } } if (n!=1) ++cc; if (cc!=1) puts("-1"); else { n = p; solve(); } } } return 0; }