求原根

题目描述：

原根个数：满足{ (xi mod p) | 1 <= i <= p-1 } == { 1, …, p-1 }的x称为模p的原根。给出模p，求原根个数

题解：

原根的定义搞到n(x) = phi(phi(x)).)所有的奇素数都是有原根的

重点：

原根怎么得到?下面的证明:
假设奇素数n的原根为r,那么r,r^1,r^2…r^phi(n)是模n不同于的，
由于(r^i)^(phi(n))=(r^phi(n))^i=1(mod n)，1<=i<=phi(n)，所以对于r^2,r^3..r^phi(n)来说ord(sub n) a|phi(n),即phi(n)是r^i模n的阶的倍数
又因为只有当(i,phi(n))=1时，r^i才是模n的原根，所以一共有phi(phi(n))个原根。
理解:也就是说,r是一个原根的话,那么对于r^i的每一个i,只有和phi(n)互质的r^i才是另一个原根.而且因为都不一样,所以就有phi(phi(n))个.那么额外的信息:如果知道了一个原根,区它的次方和phi互质的就是另一些原根

代码：

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define CLR(a) memset(a, 0, sizeof(a)) #define REP(i, a, b) for(int i = a;i < b;i++) #define REP_D(i, a, b) for(int i = a;i <= b;i++) typedef long long ll; using namespace std; const int maxn = 1e5 + 100; int phi[maxn]; int n; vector<int> prime; int vis[maxn]; int key = 1e5; void getPhi()//欧拉筛 { CLR(vis); phi[1] = 0; REP(i, 2, key) { if(!vis[i]) { prime.push_back(i); phi[i] = i - 1; } for(int j = 0;j < prime.size() && prime[j]*i <= key;j++) { int tmp = prime[j]*i; vis[tmp] = 1; if(i%prime[j]) { phi[tmp] = (prime[j]-1)*phi[i]; } else { phi[tmp] = prime[j]*phi[i]; break; } } } } void solve() { printf("%d ", phi[n-1]); } int main() { // freopen("2Bin.txt", "r", stdin); //freopen("3Bout.txt", "w", stdout); getPhi(); while(scanf("%d", &n) != EOF) { solve(); } return 0; }