51Nod-1135-原根

2019-04-14 20:26发布

站内文章 / 模拟电子
15801 0 1215
1135 原根 题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135 题目：
设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数） 给出1个质数P，找出P最小的原根。 Input
输入1个质数P(3 <= P <= 10^9)
Output
输出P最小的原根。
input示例 3 Output示例 2 题意：给定一个质数，求最小原根。 题解：此题需要用到的公式及概念有，P为质数，则phi(p)=p-1；    a模m的阶及即满足a^r≡(1 mod m)的最小r；  存在定理：若p-1因分解p1,p2...pk，若a^((p-1)/pi)%p！=1，对1<=i<=k均成立，则a为p的原根，所以枚举 a，找到最小的a即可，注意数据范围会爆int。 AC代码： /* * @Author: 王文宇 * @Date: 2017-10-21 01:36:04 * @Last Modified by: 王文宇 * @Last Modified time: 2017-10-21 03:01:35 */ #include #include using namespace std; const int maxn = 1e7; #define ll long long ll p,t; ll is[maxn]; void pr(int n) { t=1; for(int i=2;i<=sqrt(n+0.5);i++) { if(n%i==0) { is[t++]=i; while(n%i==0)n/=i; } if(n==1)break; } if(n>1)is[t++]=n; } ll mi(ll a,ll b,ll c) { ll ans =1; if(b==0)return 1; ans=mi(a,b/2,c); ans=ans*ans%c; if(b&1)ans=ans*a%c; return ans; } int main() { ll p; scanf("%lld",&p); pr(p-1); ll i; ll ok; for(i=2;i<=p;i++) { ok=1; for(ll j=1;j

热门文章