1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
|
#include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #define INF 2000000000 using namespace std; typedef long long ll; int (){ int f = 1, x = 0; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); } while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar(); return f * x; } int p, pri[105], cnt, ans[1000005], len; int phi[1000005], prime[500005], tot = 0; bool vis[1000005] = {0}, ok[1000005] = {0}; void getPhi(int N){ phi[1] = 1; for(int i = 2; i <= N; ++i){ if(!vis[i]){ prime[++tot] = i, phi[i] = i - 1; if(i & 1){ for(int j = i; ; j *= i){ ok[j] = true; if(j + j <= N) ok[j + j] = true; if(1ll * j * i > N) break; } } } for(int j = 1; j <= tot; ++j){ ll t = 1ll * i * prime[j]; if(t > N) break; vis[t] = true, phi[t] = phi[i] * (prime[j] - 1); if(i % prime[j] == 0){ phi[t] += phi[i]; break; } } } } int poww(int a, int b, int M){ int res = 1; while(b){ if(b & 1) res = (1ll * res * a) % M; a = (1ll * a * a) % M, b >>= 1; } return res; } void getFac(int x){ cnt = 0; int t = x; for(int i = 1; i <= 168; ++i){ if(t % prime[i] == 0){ do{ t /= prime[i]; }while(t % prime[i] == 0); pri[++cnt] = prime[i]; } if(t == 1) break; } if(t != 1) pri[++cnt] = t; } bool judge_pr(int x){ if(poww(x, phi[p], p) != 1) return false; for(int i = 1; i <= cnt; ++i) if(poww(x, phi[p] / pri[i], p) == 1) return false; return true; } int get_pr(int p){ for(int i = 2; i <= p; ++i) if(judge_pr(i)) return i; return -1; } int gcd(int a, int b){ return (!b) ? a: gcd(b, a % b); } void solve(){ if(p == 1 || p == 2) { printf("1n"); return ; } if(p == 4) { printf("3n"); return ; } if(!ok[p]){ printf("-1n"); return ; } getFac(phi[p]); int res = get_pr(p); len = 0, ans[++len] = res; for(int i = 2, j = 1ll * res * res % p; i < phi[p]; ++i, j = 1ll * j * res % p){ if(gcd(i, phi[p]) == 1) ans[++len] = j; } sort(ans + 1, ans + len + 1); for(int i = 1; i < len; ++i) printf("%d ", ans[i]); printf("%dn", ans[len]); } int main(){ getPhi(1000000); while(~scanf("%d", &p)){ solve(); } return 0; }
|
近期评论