数论
1135 原根 1 秒 131,072 KB 0 分 基础题设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数）
给出1个质数P，找出P最小的原根。
收起
输入 输入1个质数P(3 <= P <= 10^9) 输出 输出P最小的原根。 输入样例 3 输出样例 2为欧拉函数
#include<set>#include<map>#include<list>#include<queue>#include<stack>#include<math.h>#include<vector>#include<bitset>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream>#include<algorithm>#define eps (1e-8)#define MAX 0x3f3f3f3f#define u_max 1844674407370955161#define l_max 9223372036854775807#define i_max 2147483647#define re register#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]#define nth(k,n) nth_element(a,a+k,a+n); // 将 第K大的放在k位#define ko() for(int i=2;i<=n;i++) s=(s+k)%i // 约瑟夫using namespace std;inline int read(){ char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' & c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f;}typedef long long ll;const double pi = atan(1.)*4.;const int M=1e3+5;const int N=1e6+5;int a[N],p=0;void fun(int n){ for(int i=2;i*i<=n;i++){ if(n%i==0){ a[p++]=i; while(n%i==0) n/=i; } } if(n!=1) a[p++]=n; return ;}ll po_w(ll a,ll b,ll mod){ ll ans=1; while(b){ if(b&1) ans=ans*a%mod; b>>=1; a=a*a%mod; } return ans%mod;}int main(){ int n; scanf("%d",&n); fun(n-1); for(int i=2;i<n;i++){ int leap=0; for(int j=0;j<p;j++){ int t=(n-1)/a[j]; ll ans=po_w(i,t,n); if(ans%n==1){ leap=1; break; } } if(!leap){ printf("%dn",i); break; } } return 0;}