51nod 1135 原根 （数论）

51nod 1135 原根 （数论）

题目链接： ​​​原根例题​​

求模素数P原根的方法：对

素因子分解，即

是P−1的标准分解式，若恒有

成立，则

就是

的原根。（对于合数求原根，只需把

换成

即可）。

代码：

#include using namespace std;int p[100010];int t = 0;void divide(long long n){ for(int i = 2; i * i <= n; i++){ if(n % i == 0){ p[t ++] = i; while(n % i == 0) n /= i; } }}int solve(long long x,long long n,long long m){ long long res = 1; while(n > 0){ if(n & 1) res = (res * x) % m; x = (x * x) % m; n >>= 1; } return res;}int main(){ long long a; cin >> a; divide(a - 1);//求a-1所有的质因子 for(int i = 2; i < a; i++) { bool flag = false; for(int j = 0; j < t; j++) { if(solve(i,(a - 1) / p[j], a ) == 1)//判断是否是原根 { flag = true; break; } } if(!flag){ cout << i << endl; break; } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。