[백준 11689] GCD(n, k) = 1

 

 수학적 개념을 알고 있으면 쉽고, 모른다면 어려운 문제. 오일러 피 함수에 대해 알고 있다면 쉽게 구현할 수 있다. 나는 그 존재에 대해서 잘 몰랐는데, 풀고 나서 찾아보니 오일러 피 함수를 이용해서 푼 상태였다.

 일단 문제는 1~n 범위 내에서 최대공약수가 1인 k를 모두 찾는 것인데, 이는 서로소를 찾으라는 것과 동치다(그리고 이것은 오일러 피 함수의 개념 그 자체다..). 

 

 나는 n의 범위를 보고, 이게 선형 탐색도 쓸 수 없는 조건이라는 점에서 착안해, 서로소를 하나하나 찾아낼게 아니라 n의 인수들을 이용해 n 값에서 빼면서 서로소 개수만 알아내야겠다는 생각이 들었다. 어떻게 보면 에라토스테네스의 체를 배열 없이 개수에 대한 정보만 남겨 사용하는 느낌이다. 인수 쌍은 sqrt(n)까지만 탐색하면 그 개수를 알 수 있으니까 하는 생각에서였는데, 그렇게 접근하려니 한 인수가 앞서 등장한 다른 작은 인수를 자신의 인수로 할 때가 떠올라서 아차 싶었다.

 

 그래서 소인수만 사용해야겠다는 생각으로 로직을 다시 작성했다.

 

 이런 로직인데, 2부터 sqrt(n)까지 n에 대한 인수인지 판별해서 인수라면, 그 인수로 만들 수 있는 모든 케이스를 res에서 빼준다(GCD가 1이 아니라는 의미이므로). 그리고 추후 중복된 인수 계산을 막기 위해 i를 소인수 취급해서 n에서 모두 날려버린다. n%i==0이라면, 계속해서 n /= i를 해서 n에 존재하던 i를 전부 없애는 방법으로 구현했다. 2부터 순차적으로 계산하고 있는 상황이므로, 결과적으로 소인수 분해했을 때 소인수 i에 대한 항을 나눠 없앤 꼴이 된다. 

 그리고 남은 n(다른 더 큰 소인수로 이루어진 항만 남은 값)에 대해 루프를 마저 진행한다. 이렇게 되면 결국 마지막 소인수만 남아 n이 1보다 크거나 1이 되는데(하나의 소인수와 그 거듭제곱 꼴로 이뤄진 수인 경우 거나 애초 입력부터 1인 경우), 마지막 소인수가 남은 경우에는 res에서 res/n을 한번 더 빼주어서 해당 소인수로 만들어지는 k 케이스들을 제외해 준다.

 

 되게 골 아프게 구현했는데, 정수론에 대해 잘 알았다면 금방 풀었겠다 싶다.. 코드로 나타내면 아래와 같다.

#include <iostream>

using namespace std;

int main() {
    long long n;
    cin >> n;

    long long result = n;
    for(long long i=2; i*i<=n; i++) {
        if(n%i==0) {
            result -= result/i;
            while(n%i==0) n /= i;
        }
    }

    if(n>1) result -= result/n;
    cout << result;
}