51nod 1135 原根 就是原根...

本文主要是介绍51nod 1135 原根 就是原根...，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

%%% dalao Orz ,筛素数到sqrt(n),分解$\phi(p)$，依次枚举判断就好了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 100000
#define LL long long
using namespace std;
LL prime[100010],tot,cnt,p[100010],n;
bool bo[100010],flag;
void init(){for(int i=2;i<=N;i++){if(!bo[i])prime[++tot]=i;for(int j=1;j<=tot&&i*prime[j]<=N;j++){bo[i*prime[j]]=1;if(i%prime[j]==0)break;}}
}
void divide(int x){cnt=0;for(int i=1;prime[i]*prime[i]<=x;i++){if(x%prime[i]==0){p[++cnt]=prime[i];while(x%prime[i]==0)x/=prime[i];}}p[++cnt]=x;
}
LL qpm(LL x,LL y,LL z){LL ans=1;while(y){if(y&1) ans=(ans*x)%z;x=(x*x)%z;y>>=1;}return ans;
}
int main(){scanf("%lld",&n);init();divide(n-1);for(int i=2;i<n;i++){flag=0;for(int j=1;j<=cnt;j++){LL tmp=(n-1)/p[j];if(qpm(i,tmp,n)==1){flag=1;break;}}if(!flag){printf("%d\n",i);break;}}return 0;
}

这篇关于51nod 1135 原根 就是原根...的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---