GCD(n, k) = 1

Problem link: https://www.acmicpc.net/problem/11689

그닥 어려운 문제는 아니었지만, 여러 개념들을 복기해내야해서 나름대로 애를 먹었다.

배울게 많아 좋은 문제라는 생각이 들어 조금은 공을 들여 기록을 남겨본다.

참고로, 이 문제는 Euler's phi 함수를 사용하면 매우 쉽게 풀 수 있다.

다만, 함수를 사용해서 풀다보면 배우고 지나가면 좋을 개념들을 쉽게 지나칠 수 있다.

따라서, 이 포스팅에서는 Euler's phi 함수를 사용하지 않고 풀이를 적어보려한다(글의 끝에 알게될테지만 원리는 같다).

Insight

문제를 풀기 위한 최초의 insight는 몇 번 손으로 풀어보면서 힌트를 얻을 수 있다.

중요한 직관은 GCD(n, k) = 1인 k의 갯수는 n(전체 자연수의 갯수)에서 n의 소인수의 배수들의 갯수를 빼준 것과 같다는 사실이다.

예를 들어, n == 45인 경우 n의 소인수는 factors={3, 5}임을 알 수 있다.

n 이하 자연수들 중 3 또는 5의 배수의 수를 빼준다면 답은 곧 answer == 45 - 45/3 - 45/5 + 45/15 == 24가 됨을 알 수 있다.

factors 구하기

이제, 주어지는 n의 소인수 리스트(i.e. factors)를 구하는 방법을 생각해보자.

당연히, 에라토스테네스 체를 이용하면 쉽게 구할 수 있는데 n의 범위가 10^12으로 꽤나 커서 단순한 방법을 사용하기에는 무리가 있다.

이 때 사용할 수 있는 한 가지 좋은 성질이 있는데, 이는 아래와 같다.

• n의 소인수는 모두 sqrt(n)보다 작거나 같거나, 단 하나만이 sqrt(n)보다 크다.
  • 증명은 귀류법으로 간단히 가능한데, 만약 n이 sqrt(n)보다 큰 2개 이상의 소인수를 갖는다고 하자.
  • 편의상 이들 중 2개를 f0, f1라고 하자.
  • 그렇다면, n == f0 * f1 * ...와 같이 표현할 수 있다는 이야기인데, f0, f1이 모두 sqrt(n)보다 크다면 n < f0 * f1 * ...이 되어 가정에 모순이다.

본격적으로, 상술한 성질을 바탕으로 n의 factors를 구해보자.

• n의 factors를 구하기 위해서는 우선 sqrt(n)이하의 소수들을 에라토스테네스 체를 이용하여 구해놓자.
• 체를 통해 구해놓은 소수중에서 n의 소인수를 만날 때마다, 발견한 소인수를 factors에 넣어주고, n을 구한 소인수로 계속 나누어서 찾은 소인수 성분을 제거해주자.
• 다음 후보 소수에 대해서 이를 반복했을 때, 마지막에 n이 1이 아니라면 이 수가 sqrt(n)을 초과하는 소인수가 될 것이다.
• 말로 풀면 복잡한데, 이를 코드로 풀어보면 아래와 같다.

div = n
for i in range(2, sqrt(n) + 1):
    if div % i == 0 and is_prime[i]: # i가 div의 소인수라면,
        factors.append(i) # i는 자명하게 n의 소인수이다.
        while div % i == 0: # i를 더이상 소인수로 가지지 않을 때까지 나누자
            div = div / i
if div != 1: # sqrt(n) 보다 큰 단 하나의 소인수가 존재하는 경우
    factors.append(div)
        

배수의 갯수 세기

factors를 구한 뒤에는 n에서 factor[0]의 배수, factor[1]의 배수, ...을 모두 빼주어야 한다.

공배수 문제가 있기 때문에, 여기서는 포함-배제 원리를 사용해주어야만 한다.

홀수개 집합은 더하고, 짝수개 집합은 뺀다로 기억하면 편리한 원리인데, 자세한 내용은 링크를 참조하면 된다.

내 풀이에서는 비트마스크를 활용해서 집합을 표현했다.

#include <iostream>
#include <cstdint>
#include <vector>

using namespace std;

const int kSqrtMaxN = 1000000;

int64_t N;
bool IS_COMP[kSqrtMaxN + 1];

void DoSieve(void)
{
  for (int64_t i = 2; i <= kSqrtMaxN; ++i)
  {
    if (!IS_COMP[i])
    {
      for (int64_t j = i * i; j <= kSqrtMaxN; j += i)
      {
        IS_COMP[j] = true;
      }
    }
  }
}

int64_t Solve(void)
{
  vector<int64_t> factors;

  int64_t n = N;
  for (int64_t i = 2; i * i <= N; ++i)
  {
    if (n % i == 0 && !IS_COMP[i])
    {
      factors.emplace_back(i);

      while (n % i == 0)
      {
        n /= i;
      }
    }
  }

  if (n != 1)
  {
    factors.emplace_back(n);
  }

  int64_t sum = 0;

  for (int mask = 1; mask < (1 << factors.size()); ++mask)
  {
    int64_t lcm = 1;
    int64_t number_of_sets = 0;

    for (int bit = 0; (1 << bit) <= mask; ++bit)
    {
      if (mask & (1 << bit))
      {
        lcm *= factors[bit];
        ++number_of_sets;
      }
    }

    if (number_of_sets % 2)
    {
      sum += N / lcm;
    }
    else
    {
      sum -= N / lcm;
    }
  }

  return N - sum;
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  cin >> N;

  // Solve
  DoSieve();
  cout << Solve() << '\n';

  return 0;
}