オイラー関数

// オイラー関数ではn以下のnと互いに素な自然数の個数を求めます。
// O(N^(1/2))
long long euler_phi(ll n){
  long long res = n;
  for(long long i = 2; i*i <= n; i++){
    if(n % i == 0){
      res = res / i * (i-1);
      for(;n % i == 0; n /= i);
    }
  }
  if(n != 1)res = res / n * (n-1);
  return res;
}

// テーブルの作成 O(MAX_N)程度
long long euler[MAX_N];

void euler_phi(){
  for(long long i = 0; i < MAX_N; i++)euler[i] = i;
  for(long long i = 2; i < MAX_N; i++){
    if(euler[i] == i){
      for(long long j = i; j < MAX_N; j += i)euler[j] = euler[j] / i *(i-1);
    }
  }
}