Euler's Phi Function | Aizu Online Judge http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_D

NTL_1_D.cpp

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

// 素因数分解
vector<pair<int,int> > prime_division(int n) {
  vector<pair<int,int> > pv;
  for (int i = 2; i <= sqrt(n) ; i++) {
    int k = 0;
    while (n % i == 0) {
      k++;
      n /= i;
    }
    if (k > 0)
      pv.push_back(make_pair(i, k));
  }
  if (n != 1)
    pv.push_back(make_pair(n, 1));
  return pv;
}

int power(int x, int e) {
  int prod = 1;
  while (e > 0) {
    if (e % 2 == 1) 
      prod = prod*x;
    x = x*x;
    e /= 2;
  }
  return prod;
}

int main(){
  int n, ans = 1;
  vector<pair<int,int> > pv;
  cin >> n;
  pv = prime_division(n);
  for (int i = 0; i < pv.size(); i++)
    ans *= power(pv[i].first, pv[i].second-1)*(pv[i].first-1);
  cout << ans << endl;
  return 0;
}