poj - 1284 - Primitive Roots

题意：题意映射为求p-1的欧拉函数。

题目链接：http://poj.org/problem?id=1284

——>>直接求单个数的欧拉函数。

#include <cstdio>
#include <cmath>using namespace std;int main()
{int p, i;while(~scanf("%d", &p)){p--;int m = (int)sqrt(p+0.5), ans = p;for(i = 2; i <= m; i++) if(p % i == 0){ans = ans / i * (i-1);while(p % i == 0) p /= i;}if(p > 1) ans = ans / p * (p-1);printf("%d\n", ans);}return 0;
}