Problem xxx. ABC

Brief description:

…

Analysis:

…

External link:

Problem 1004. Primitive Roots

Brief description:

求 n 的所有原根。

Analysis:

…
注意常数。

int getPrimitive(int n){
    int p = phi[n]; VI d; for (int i=2;i*i<=p;++i) if (!(p%i)) d.PB(i), d.PB(p/i);

    bool fb = 1;

    UNQ(d); MOD = n; FOR(i, 2, n) if (pow(i, p) == 1){
        int j = 0; REP_N(j, SZ(d)) if (pow(i, d[j]) == 1) break;

        if (j == SZ(d)){
            if (!fb) putchar(' '); fb = 0;
            cout << i;
        }
    }
    return 0;
}

//}/* .................................................................................................................................. */

const int PMAX = 1000009;
VI P; bitset<PMAX> isC; int phi[PMAX], min_p[PMAX];
#define ii (i*P[j])
void sieve(){
    phi[1] = 1; FOR(i, 2, PMAX){
        if (!isC[i]) P.PB(i),min_p[i]=i,phi[i]=i-1;
        for (int j=0;j<SZ(P)&&ii<PMAX;++j){
            isC[ii]=1,min_p[ii]=P[j]; if (i%P[j]==0){
                phi[ii] = phi[i]*P[j];
                break;
            }
            else{
                phi[ii] = phi[i]*P[j]-phi[i];
            }
        }
    }
}
#undef ii


int getPrimitive(int n){
    int p = phi[n]; VI d;
    for (int i=2;i*i<=p;++i) if (p%i==0){
        d.PB(i); do p/=i;while(p%i==0);
    }
    if (p>1)d.PB(p);

    p = phi[n]; MOD = n; FOR(i, 2, n) if (pow(i, p) == 1){
        int j = 0; REP_N(j, SZ(d)) if (pow(i, p/d[j]) == 1) break;
        if (j == SZ(d)) return i;
    }
    return 0;
}


bool ck(int n){
    if (n == 4) return 1;
	if(n%2==0)n/=2;if(n%2==0) return 0;
	int p=min_p[n]; do n/=p; while (n%p==0);
	return n==1;
}

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    sieve();

    int n; while (~scanf("%d", &n)){
        if (n <= 2) puts("1");
        else if (!ck(n)) puts("-1");
        else{
            MOD = n; int g = getPrimitive(n), p = phi[n]; VI G;
            REP_1(i, p/2) if (gcd(i, p-i) == 1) G.PB(pow(g, i)),G.PB(pow(g, p-i));
            UNQ(G); printf("%d", G[0]); FOR(i, 1, SZ(G)) printf(" %d", G[i]);
            puts("");
        }
    }
}

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

#define PB push_back
#define MP make_pair
#define AA first
#define BB second
#define OP begin()
#define ED end()
#define SZ size()
#define SORT(x) sort(x.OP,x.ED)
#define SQ(x) ((x)*(x))
#define SSP system("pause")
#define cmin(x,y) x=min(x,y)
#define cmax(x,y) x=max(x,y)
typedef long long LL;
typedef pair<int, int> PII;
const double eps=1e-8;
const double PI=acos(-1.);
const LL MOD = 1000000007;
LL powMod(LL a,LL b,LL m) {
	LL ret=1;
	while(b) {
		if(b&1)ret=ret*a%m;
		a=a*a%m;
		b>>=1;
	}
	return ret;
}
int eulerPhi(int n) {
	int res = n;
	for(int i = 2; i * i <= n; i++)
		if(n % i == 0) {
			res = res / i * (i - 1);
			for(; n % i == 0; n /= i);
		}
	if(n != 1) res = res / n * (n - 1);
	return res;
}
int find_root(int P) {
	if(P==2)return 1;
	int Q=eulerPhi(P);
	int phi=Q;
	vector<int>G;
	int i,j;
	for(i=2; i*i<=Q; i++)if(Q%i==0) {
			G.PB(i);
			while(Q%i==0)Q/=i;
		}
	if(Q>1)G.PB(Q);
	for(i=2;; i++)if(powMod(i,phi,P)==1) {
			int flag=1;
			for(j=0; j<G.SZ; j++)if(powMod(i,phi/G[j],P)==1) {flag=0; break;}
			if(flag)return i;
		}
	return -1;
}
bool check(int n) {
	vector<PII>L;
	int cnt=0;
	while(n%2==0)n/=2,cnt++;
	if(cnt>1)return 0;
	int i;
	for(i=3; i*i<=n; i++)if(n%i==0)break;
	if(n%i==0) {
		while(n%i==0)n/=i;
		if(n>1)return 0;
		return 1;
	}
	return 1;
}
int __gcd(int a,int b) {
	return b?__gcd(b,a%b):a;
}
int main() {
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	int i,j,k,T;
	int n;
	while(cin>>n) {
		if(n==1) {
			printf("1\n");
			continue;
		}
		if(n==2) {
			printf("1\n");
			continue;
		}
		if(n==4) {
			printf("3\n");
			continue;
		}
		if(!check(n)) {
			printf("-1\n");
			continue;
		}
		int __=find_root(n);
		int Q=eulerPhi(n);
		vector<int>L;
		for(i=1; i+i<=Q; i++)if(__gcd(i,Q-i)==1) {
				L.PB(powMod(__,i,n));
				L.PB(powMod(__,Q-i,n));
			}
		sort(L.OP,L.ED);
		L.erase(unique(L.OP,L.ED),L.ED);
		printf("%d",L[0]);
		for(i=1; i<L.SZ; i++)printf(" %d",L[i]);
		printf("\n");
	}
	return 0;
}

Posted by xiaodao
Category: 日常