51nod 1135 原根

题目链接:51nod 1135 原根 设 m 是正整数，a是整数，若a模m的阶等于φ(m)，则称 a 为 模m的一个原根。（其中φ(m)表示m的欧拉函数） 阶：gcd(a,m)=1,使得这里写图片描述成立的最小的 r，称为 a 对 模m 的 阶。 φ(m)：在[1,m)的区间内与m互质的数的个数(详细见百科欧拉函数) 求模素数p的原根a的方法： 因为p为素数，所以φ(p)=p-1, 这题就是要找最小的a使得 a^(p-1)%p = 1 成立（根据费马小定理，该式一定成立）， 算法流程如下: ①先求p-1所有不同的 质因子 p1,p2…pm ②对任何整数 a ∈[1,p-1]， 检验 a 是否为 p 的原根 检验方法：a^((p-1)/p1),a^((p-1)/p2),…a^((p-1)/pm) 中是否存在一个 模p 等于 1 ， 存在的话 a 就不是 模p 的一个原根（即p-1就不是a对模p的阶），否则a就为原根。 源代码 #include #include #include #include #include #include #define CLR(a,b) memset((a),(b),sizeof((a))) using namespace std; typedef long long ll; const int N = 50000; int prime[N];//prime[0] 存的是素数的个数 int ppri[N];//p-1的质因子 void getPrime(){ CLR(prime , 0); for(int i = 2;i < N; i++){ if(!prime[i]) prime[ ++prime[0] ] = i; for(int j = 1; j <= prime[0] && prime[j] <= N / i; j++){ prime[ prime[j] * i ] = 1; if(i % prime[j] == 0) break; } } } ll pow_m(ll a, ll n, ll m){ //大指数取模运算 ll t = a % m; //指数最高级别 ll r = 1; while(n > 0){ if(n & 1) //if(n%2==1) r = r * t % m; t = t * t % m; n >>= 1; //n=n/2 } return r; } int divide(int n){//分解合数n的质因子 int cnt = 0; for(int i = 1; prime[i] * prime[i] <= n; ++i){ if(n % prime[i] == 0){ ppri[++cnt] = prime[i]; while(n % prime[i] == 0){ n /= prime[i]; } } } if(n > 1) ppri[++cnt] = n; return cnt; } int main(){ int p, i, a, t, f; getPrime(); scanf("%d", &p); int cnt = divide(p - 1);//p-1 的 质因子个数 for(a = 2; a <= p - 1; ++a){//原根从 2 到 p-1 枚举 f = 1; for(i = 1; i <= cnt; ++i){ t = (p - 1) / ppri[i]; if( pow_m(a, t, p) == 1){ //存在a^((p-1)/ppr[i]) mod p = 1， 则 a 不是质数p的原根 f = 0; break; } } if(f){ printf("%d ",a); break; } } return 0; } 源自:http://www.cnblogs.com/GraceSkyer/p/5990485.html 补充之一：
关于函数ll pow_m(ll a, ll n, ll m)—快速幂取模运算
快速幂算法依赖于以下明显的公式： 原理： a*b % n = (a % n)*(b % n) % n
举例: 2^7%3=(2*2^2*2^4)%3 int PowerMod(int a, int b, int c) { int ans = 1; a = a % c; while(b>0) { if(b % 2 = = 1) //b&1 ans = (ans * a) % c; b = b/2; //b>>=1 a = (a * a) % c; } return ans; } 本算法的时间复杂度为O（logb），能在几乎所有的程序设计（竞赛）过程中通过，是目前最常用的算法之一。
参考传送门①
参考传送门② 补充之二：一般线性素数筛选（可替代上述素数筛选(/≧▽≦)/） const int N = 50000; int prime[N];//prime[0] 存的是素数的个数 int ppri[N];//p-1的质因子 bool prime_bool[N + 1]; int cnt=0; void getPrime(){ //获取前50000个质因子 CLR(prime , 0); memset(prime_bool, 1, sizeof(prime_bool)); int i, j, T = sqrt((double)N) + 1; //一般线性筛选素数 for(i = 2; i < T; ++i) { if(prime_bool[i]) { for(j = i + i; j < N; j += i) { prime_bool[j] = false; } } } prime_bool[0] = prime_bool[1] = false; //根据标记记录素数 for(i=2;iif(prime_bool[i]){ prime[++cnt]=i; } } }