백준 11689 GCD(n, k) = 1

백준 11689번 문제 https://www.acmicpc.net/problem/11689

이 문제는 오일러 피 함수를 이용해 푸는 문제이다.

오일러 피(파이) 함수의 정의는 다음과 같다.
1. $p$가 소수인 경우

2. $p$가 소수의 거듭제곱인 경우

   $\phi(p^k) = p^{k}(1-\frac{1}{p})$

3. $n$과 $m$이 서로소인 경우

   $\phi(mn) = \phi(m)\phi(n)$

따라서, $n$을 소인수한 결과르루 이용해 오일러 피 함수를 표현하면 다음과 같다.

#include <iostream>

using namespace std;

long long n;
long long ans, num;
bool notprime = false;
void input() {
  cin >> n;
  ans = n;
  num = n;
}

void solve() {
  for (long long i = 2; i * i <= n; i++) {
    if (num % i == 0) {
      notprime = true;
      ans = ans / i * (i-1); // (1-1/i) 곱하는
   
      while (num % i == 0) {
        num /= i;    // 거듭제곱?
      }
    }
    
  }
  
  if(!notprime && n!=1){
    ans = ans - 1;
    cout << ans;
  }
  //위에를 그냥 패스하면, 소수라는 것,
  //소수일 경우, phi(p) = p - 1
  //소수의 거듭제곱일 경우, phi(p^m) = p^m(1-1/p)
  else if(num != 1) { 
    //두 경우가 아니라면, (소수도, 소수의 거듭제곱도 아니면)
    ans = ans / num * (num - 1);
    cout << ans;
  }
  else cout << ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  input();
  solve();
  return 0;
}