POJ - 1284 题意是，求一个质数的原根 原根的定义是，对于正整数 aimodp(i=[1,p−1]) a^i mod p (i=[1,p-1])得到的集合为{1,2,…,p-1}，那么则称 a是 p的一个原根 对于任意正整数 p，其原根个数为 ϕ(ϕ(p)) \phi( \phi(p) )， ϕ(n) \phi(n)为欧拉函数，表示小于n且与n互质的数的个数 而质数的欧拉函数值

题目链接 ： 传送门 题目大意： 求一个质数的原根个数。 先普及一下原根的定义： 设m是正整数，a是整数，若a模m的阶等于euler(m)，则称a为模m的一个原根。 eg: m=7，euler（7） =  6（1，2，3，4，5，6）   则： 1   1^(n)mod7=1! = 62   2^(n)mod7={2 4 1}!=6 3   3^(n)mod7={3,2,6,4,

《算法导论》练习31.6-1   ord11(1) = 1 ord11(2) = 10 ord11(3) = 5 ord11(4) = 5 ord11(5) = 5 ord11(6) = 10 ord11(7) = 10 ord11(8) = 10 ord11(9) = 5 ord11(10) = 2   因此最小原根是g=2   ind11,2(1) = 0 in

%%% dalao Orz ,筛素数到sqrt(n),分解 ϕ(p) \phi(p)，依次枚举判断就好了 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#define N 100000#define LL long longusing namespace st