51nod--1135 原根 （数论）

2019-04-13 14:08发布

站内文章 / 模拟电子
13731 0 1543

题目：

设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

分析：

原根的板子题了。
原根知识详解： 点我萌萌哒

实现：

#include using namespace std; typedef long long LL; const int maxn = 100000 + 131; vector Primes; bool Jug[maxn]; void Make_Primes() { /// 素数打表 Primes.clear(); memset(Jug, false, sizeof(Jug)); for(LL i = 2; i <= maxn; ++i) { if(Jug[i] == false) { Primes.push_back(i); for(LL j = i + i; j <= maxn; j += i) Jug[j] = true; } } } vector Pi; void GetPi(LL X) { /// 获得 x 的质因子 Pi.clear(); LL mx = Primes.size(); for(LL i = 0; i < mx && Primes[i] * Primes[i] <= X; ++i) { if(X % Primes[i] == 0) { Pi.push_back(Primes[i]); while(X % Primes[i] == 0) X /= Primes[i]; } } if(X > 1) Pi.push_back(X); } LL Pow(LL a, LL n, LL mod) { /// 快速幂取摸 LL ret = 1; while(n) { if(n & 1) ret = ret * a % mod; a = a * a % mod; n >>= 1; } return ret; } bool JugAx(LL tmp, LL P) { /// 判断 tmp 是否是 P 原根 for(int i = 0; i < Pi.size(); ++i) { if(Pow(tmp, (P-1)/ Pi[i], P) == 1) return false; } return true; } int main() { LL P; Make_Primes(); while(cin >> P) { GetPi(P-1); for(LL i = 2; i <= P-1; ++i) { if(JugAx(i, P)) { cout << i << endl; break; } } } return 0; }

热门文章