【POJ 1284】Primitive Roots

题目传送门：http://poj.org/problem?id=1284

题目大意：给一个素数（>3），求原根的个数。
相关定理：如果一个数a有原根，则个数为\(\varphi (\varphi (a))\\)
定理证明：我不会QAQ，可以参考：wiki中的性质一栏

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100000+9;
const int MX = 70000;

int pri[MAXN],tot,phi[MAXN];
bool tag[MAXN];

inline void Get_Phi(){
	phi[1] = 1;
	for (int i=2;i<=MX;i++) {
		if (!tag[i]) pri[++tot] = i, phi[i] = i-1;
		for (int j=1;j<=tot && pri[j]*i <= MX;j++) {
			tag[pri[j]*i] = 1;
			if (i % pri[j]) phi[pri[j]*i] = phi[i]*(pri[j]-1);
			else {phi[pri[j]*i] = phi[i]*pri[j]; break;}
		}
	}
}

int main(){
	Get_Phi(); int a;
	while (~scanf("%d",&a))	printf("%d\n",phi[a-1]);	
	return 0;
} 

我一定不会告诉你：其实我只是来水线性递推欧拉函数的QAQ