一些模板

1e12找原根板子

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,prime[1000005],is_prime[1000005],cnt,qv[1000005],qn[1000005],top,g,Phi,sum,ans[1000005],mod;
void fj(ll x){
	top=0;
	for(ll i=1;prime[i]*prime[i]<=x;i++){
		if(x%prime[i]==0)qv[++top]=prime[i],qn[top]=0;
		while(x%prime[i]==0)qn[top]++,x/=prime[i];
	}
	if(x!=1)qv[++top]=x,qn[top]=1;
}
ll phi(ll x){
	ll ans=x;
	for(ll i=1;prime[i]*prime[i]<=x;i++){
		if(x%prime[i]==0)ans=ans/prime[i]*(prime[i]-1);
		while(x%prime[i]==0)x/=prime[i];
	}
	if(x!=1)ans=ans/x*(x-1);
	return ans;
}
ll ksm(ll A,ll B){
	ll Ans=1;
	while(B){
		if(B%2)Ans=Ans*A%mod;
		B/=2;
		A=A*A%mod;
	}
	return Ans;
}
bool check(ll x){
	if(ksm(x,Phi)!=1)return 0;
	for(ll i=1;i<=top;i++){
		if(ksm(x,Phi/qv[i])==1)return 0;
	}
	return 1;
}
void init(){
	for(ll i=2;i<=1e6;i++){
		if(!is_prime[i])prime[++cnt]=i;
		for(ll j=1;j<=cnt&&i*prime[j]<=1e6;j++){
			is_prime[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
int main(){
	init();
	scanf("%lld",&n);
	mod=n;
	if(n%2==0&&n!=2&&n!=4){
		fj(n/2);
		if(top>1){
			printf("0\n");
			return 0;
		}
	}
	else if(n!=2&&n!=4){
		fj(n);
		if(top>1){
			printf("0\n");
			return 0;
		}
	}
	Phi=phi(n);
	fj(Phi);
	for(ll i=1;i<n;i++){
		if(check(i)){
			g=i;
			break;
		}
	}
	for(int i=1;i<Phi;i++){
		if(gcd(i,Phi)==1){
			ans[++sum]=ksm(g,i);
		}
	}
	printf("%d\n",sum);
	sort(ans+1,ans+1+sum);
	for(int i=1;i<=sum;i++)printf("%d ",ans[i]);
}