阶
定义：
设，那么使得
成立的最小正整数
就称为
模
的阶.记作
并且
总是可以整除
即
由定义，,故有
因此
原根
定义：
一个数的结果两两不相同，其中，
如果，那么当
的阶
时，称
就是在多个其中
是使得
的最小正整数就称
但是其中只有和
是模
的原根.
质数
给出一个质数
将其中
都是质数
然后枚举
则原根性质：
- 所有的质数
都可以找到原根，且个数是
)
- 不是所有的整数都有原根
- 若模
这些形式的一种，其中
- 若模
))
- 模
的。所以有些东西你枚举就够了
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1e5+10;
int p[M],cnt;
void ol(ll n)//将φ(m)唯一定理分解
{
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
p[cnt++]=i;
}
while(n%i==0)
{
n/=i;
}
}
if(n>1)
{
p[cnt++]=n;
}
return ;
}
ll qpow(ll a,ll n,ll mod)
{
ll ans=1;
ll base=a;
while(n)
{
if(n&1)
{
ans=ans*base%mod;
}
base=base*base%mod;
n>>=1;
}
return ans%mod;
}
ll query(ll n)
{
if(n==2||n==4)
{
return n-1;
}
cnt=0,ol(n-1);
for(int i=2;i<n;i++)//从小到大遍历a
{
int flag=1;
for(int j=0;j<cnt;j++)
{
if(qpow(i,(n-1)/p[j],n)==1)//根据原根求法
{
flag=0;
break;
}
}
if(flag==1)//输出最小的原根
{
return i;
}
}
}
int main( )
{
ll n;
while(~scanf("%lld",&n))
{
printf("%lld\n",query(n));
}
return 0;
}
