서로소의 개수

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

풀이를 잘 떠올리지 못해서 답을 보고 풀었다.

답을 본 직후에도 "무슨 소리지?" 고민했던 것을 보면 오히려 빨리 답을 본 것이 다행인가 싶다.

이 문제는 DP로 접근해서 풀 수 있는데, DP 풀이를 기술하기에 앞서서 아래의 lemma 하나를 짚고 넘어가도록 하자.

주어진 숫자가 num[1..N] 이라고 해보자.

임의의 i(1<=i<N)에 대해서 gcd(num[1], num[2], .., num[i]) == x였다고 가정해보자.

num[1], num[2], .., num[i]에 num[i+1] 숫자 하나를 추가해서 최대공약수가 k가 되고 싶다면 num[i+1]은 어떤 성질을 만족해야할지를 떠올려보자.

(즉, gcd(num[1], num[2], .., num[i], num[i+1]) == k가 되게하는 방법)

잘 생각해보면 gcd(num[i+1], x) == k임을 알 수 있다.

당연한듯 하지만 의외로 "설명해보세요"하면 얼탈 수 있는 내용이다.

아래와 같이 정성적으로 증명해보자.

• case 1) num[i+1]을 추가해서 최대공약수가 더 커질 수 있는가(즉, x < k 일 수 있는가?)?
  • 자명하게 NO이다.
  • 만약 더 커질 수 있다면, x가 num[1], num[2], .. num[i]의 최대공약수였다는 사실에 모순이다.
• case 2) num[i+1]을 추가해서 최대공약수가 더 작거나 같아질 수 있는가(즉, x >= k일 수 있는가?)?
  • 가능하다.
  • gcd(num[i+1], x) == k 였다면 얼마든지 가능한 경우이다.
  • 보다 엄밀히 이야기하면, num[1] | x, num[2] | x, ... num[i] | x인데 num[i+1] !| x(not divisible)인 경우를 떠올리면 된다.

이제 위의 lemma를 가지고 DP 풀이를 만들어보자.

아래와 같이 캐시를 정의하자.

• DP[i][j]: i번째 수까지 사용할 때 최대공약수가 j인 부분집합의 수

num[i]를 포함할 것이냐 안 할것이냐를 기준으로 아래와 같은 점화식을 세우는 것이 가능하다.

• DP[i][j] = DP[i-1][j] + DP[i-1][k](단, gcd(num[i], k) == j)

첫 번째 항은 자명하게 num[i]를 포함하지 않는 경우를 헤아려 준 것이다.

두 번째 항이 바로 상술했던 lemma를 사용한 것인데, num[i]를 포함해도 여전히 최대공약수가 j가 되는 경우를 헤아려준 것이다.

하지만, 본격적으로 코드를 작성해보면 골 때리리는 부분이 발생하는데, 이를 아래의 의사코드(라고 쓰지만 파이썬)을 통해 살펴보도록 하자.

### Initialize
for i in range(N):
    DP[i][num[i]] = 1 # 원소의 수가 단 하나인 부분집합들 처리

for i in range(1, N):
    for j in range(1, 100001):
        DP[i][j] += DP[i-1][j]
        for k in range(1, 100001):
            if gcd(num[i], k) == j:
                DP[i][j] += DP[i-1][k]

조금이라도 빨리 풀어보겠다고 DP를 사용했는데, 끔찍하게도 3중 for loop이 등장해버렸다.

이를 개선하기 위해서 알고리즘을 조금 개선해보자.

개선의 주된 아이디어는 numS[i]를 포함하는 경우를 헤아리는 점화식과 포함하지 않는 경우를

gcd(numS[i], k) == j일 때 마지막 루프의 바디를 수행하므로 일단 아래와 같이 루프를 수정할 수 있다.

### Initialize
for i in range(N):
    DP[i][num[i]] = 1 # 원소의 수가 단 하나인 부분집합들 처리

for i in range(1, N):
    for j in range(1, 100001):
        DP[i][j] += DP[i-1][j]

        for k in range(1, 100001):
            if gcd(num[i], k) == j:
                DP[i][gcd(numS[i], k)] += DP[i-1][k]

아니 근데, 코드를 적어보니 뭔가 매우 멍청하게 동작하고 있다.

if gcd(num[i], k) == j:절이 과연 꼭 필요한지 생각해보자.

어차피 두번째 루프에서 j가 gcd(num[i], k)로 나올 수 있는 모든 값들을 루프로 순회하고 있다.

이 말인 즉슨 위의 코드를 아래와 같이 고쳐도 아무런 문제가 되지 않는다는 것이다.

### Initialize
for i in range(N):
    DP[i][num[i]] = 1 # 원소의 수가 단 하나인 부분집합들 처리

for i in range(1, N):
    for j in range(1, 100001):
        DP[i][j] += DP[i-1][j]

        for k in range(1, 100001):
            DP[i][gcd(num[i], k)] += DP[i-1][k]

그런데 고치고 보니 3번째 루프는 j에 전혀 dependent하지 않다.

따라서, 최종적으로 아래와 같이 코드를 개선할 수 있다.

for i in range(N):
    DP[i][num[i]] = 1

for i in range(1, N):
    for j in range(1, 100001):
        DP[i][j] += DP[i][j-1]
    for k in range(1, 100001):
        DP[i][gcd(num[i], k)] += DP[i-1][k]

#include <iostream>
#include <vector>

using namespace std;

const size_t kMod = 10000003;
const size_t kMaxN = 100;
const size_t kMaxNumber = 100000;

size_t N;
vector<size_t> NUMBERS;
size_t DP[kMaxN][kMaxNumber + 1];

size_t GetGcd(size_t a, size_t b)
{
  if (a < b)
  {
    return GetGcd(b, a);
  }

  while (a % b)
  {
    size_t r = a % b;
    a = b;
    b = r;
  }

  return b;
}

size_t Solve(void)
{
  for (size_t i = 0; i < NUMBERS.size(); ++i)
  {
    DP[i][NUMBERS[i]] = 1;
  }

  for (size_t i = 1; i < NUMBERS.size(); ++i)
  {
    for (size_t j = 1; j <= kMaxNumber; ++j)
    {
      DP[i][j] += DP[i - 1][j];
      DP[i][j] %= kMod;
    }
    for (size_t k = 1; k <= kMaxNumber; ++k)
    {
      size_t g = GetGcd(NUMBERS[i], k);
      DP[i][g] += DP[i - 1][k];
      DP[i][g] %= kMod;
    }
  }

  return DP[NUMBERS.size() - 1][1] % kMod;
}

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

  // Read Input
  cin >> N;
  NUMBERS.assign(N, 1);
  for (size_t it = 0; it < N; ++it)
  {
    cin >> NUMBERS[it];
  }

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

  return 0;
}