POJ 1284 Primitive Roots

Description

We say that integer x, 0 < x < p, is a primitive root modulo odd prime p if and only if the set { (x  ⁱ mod p) | 1 <= i <= p-1 } is equal to { 1, ..., p-1 }. For example, the consecutive powers of 3 modulo 7 are 3, 2, 6, 4, 5, 1, and thus 3 is a primitive root modulo 7. 
Write a program which given any odd prime 3 <= p < 65536 outputs the number of primitive roots modulo p. 

Input

Each line of the input contains an odd prime numbers p. Input is terminated by the end-of-file seperator.

Output

For each p, print a single number that gives the number of primitive roots in a single line.

Sample Input

23 31 79

Sample Output

10 8

24

原根的个数是phi(phi(n))个，所以这题就求phi(n-1)即可。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,LL>
#define in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int mod = 998244353;
const int N = 20;
int n;

int main()
{
  while (scanf("%d", &n) != EOF)
  {
    --n; int ans = 1;
    for (int i = 2; i*i <= n; i++)
    {
      if (n % i) continue;
      n /= i; ans *= i - 1;
      while (!(n % i)) ans *= i, n /= i;
    }
    printf("%d\n", n > 1 ? ans * (n - 1) : ans);
  }
  return 0;
}