https://vjudge.net/problem/51Nod-1135#
寻找一个1e9的质数的原根
第一次做这样的题
看了别人的博客才理解的
https://blog.csdn.net/u013486414/article/details/47781857
不过还是有点不太理解原根这个东西的本质
没事，慢慢的理解
AC代码：
#include<iostream> #include<vector> using namespace std; typedef long long ll; ll quickmod(ll a,ll b,ll m){ ll ans=1; while(b){ if(b&1) ans=(ans*a)%m; b>>=1; a=a*a%m; } return ans; } ll get(ll x){ vector<ll> V; ll y=x-1; for(ll i=2;i*i<=y;++i){ if(y%i==0){ V.push_back(i); while(y%i==0){ y/=i; } } } if(y>1) V.push_back(y); for(ll i=2;i<=x-1;++i){ int flag=1; for(int j=0;j<V.size();++j){ if(quickmod(i,(x-1)/V[j],x)==1){ flag=0; break; } } if(flag==1) return i; } } int main(){ ll x; while(cin>>x){ cout<<get(x)<<endl; } }