백준 26077 - 서커스 나이트 (C++)

문제

• 문제 링크

  
   BOJ 26077 - 서커스 나이트 
  

• 문제 요약

돌고래 $N$마리의 $ID$가 주어진다.
$2 ≤ gcd(i, j)$를 만족하는 돌고래들끼리만 메시지 전파가 가능할 때, 메시지를 전달받을 수 있는 돌고래 수의 최댓값을 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ N ≤ 1,000,000$

$2 ≤ N_{ID} ≤ 1,000,000$

알고리즘 분류

• 수학(math)
• 정수론(number_theory)
• 자료 구조(data structures)
• 분리 집합(disjoint_set)
• 소수 판정(primality_test)
• 에라토스테네스의 체(sieve)

풀이

$N$의 범위를 보자. 모든 쌍을 돌아보며 $gcd()$를 돌려보면 큰일날 것 같다.
문제의 중요한 조건을 정리해보자.

$2 ≤ gcd(i, j)$를 만족하는 돌고래들끼리만 통신이 가능하다.

돌고래는 자신이 들은 메시지를 다시 다른 돌고래들에게 전달할 수 있다.

각 조건을 이용해 풀이 방향을 잡아 보도록 하자.

---

$2 ≤ gcd(i, j)$를 만족하는 돌고래들끼리만 통신이 가능하다.

$2 ≤ gcd(i, j)$ 라는 말은,
두 돌고래의 $ID_i$, $ID_j$가 가 최소 하나 이상의 소인수를 공유 해야만 통신이 가능하다는 뜻이다.

소인수분해 역시 모든 $N_i$에 대해 일일이 진행 한다면 $O(N√N)$ 이므로 다소 무리가 있다.
하지만 우린, 범위에 대한 소인수 분해를 빠르게 할 수 있는 방법을 알고 있다.
마땅한 방법이 떠오르지 않는다면 BOJ 16563 - 어려운 소인수분해 를 먼저 풀고 오도록 하자.

간단히 말하자면 $sieve$에서, 보통 임의의 수가 소수다 / 아니다의 정보만을 담는데 이게 아니라 해당 수의 가장 작은 소인수를 저장한다는 것이다.
이후 이를 이용해 소수 판별은 물론이고 소수가 아닌 수들에 대해 $O(logN)$ 수준의 소인수분해를 기대할 수 있게 된다.

---

돌고래는 자신이 들은 메시지를 다시 다른 돌고래들에게 전달할 수 있다.

집합 단위로 통신할 수 있고 병합될 수 있음에 따라, 분리 집합을 떠올렸다면 충분하다.

대표 정점을 담는$Root[]$ 외에, $max(k_1, k_2, ... k_n)$ 즉 집합의 크기를 계산해야 하므로 $Size[]$ 를 추가로 정의해 집합 크기 상태를 전이하자.
알고 있겠지만 이때는 반드시 일관된 방향으로의 $merge$가 진행 되어야 한다.

궁극적으로 모든 $N_i$에 대해,
소인수분해를 진행함과 동시에 이때 등장하는 모든 수들을 $merge$ 해주면 같은 소인수를 공유하는 다른 모든 $N_j$들이 직 / 간접적으로 $merge$되는 효과를 볼 수 있게 된다.

따라서 답은 $max(Size[1], Size[2], ... Size[n])$ 가 되겠다.

전체 코드

#include<bits/stdc++.h>
#define N 1000001
using namespace std;
 
int Rt[N], Size[N], P[N], a[N];
int n, i, j;
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (; i < N; i++) P[i] = Rt[i] = i;
    for (i = 2; i * i < N; i++)
        if (P[i] == i)
            for (j = i + i; j < N; j += i)
                if (P[j] == j)
                    P[j] = i;
}
int Find(int p) { return Rt[p] = Rt[p] == p ? p : Find(Rt[p]); }
void Merge(int p, int q)
{
    p = Find(p), q = Find(q);
    if (p > q)
        Rt[p] = q, Size[q] += Size[p];
    else if (p < q)
        Rt[q] = p, Size[p] += Size[q];
}
void Solve()
{
    cin >> n;
    for (i = 1; i <= n; i++) cin >> a[i], Size[a[i]]++;
    for (i = 1; i <= n; i++)
        for (j = P[a[i]]; a[i] ^ P[a[i]]; Merge(j, a[i] /= P[a[i]]))
            Merge(j, a[i]), Merge(j, P[a[i]]);
    cout << *max_element(Size, Size + N);
}
int main()
{
    Init();
    Solve();
}

comment

교육적이고 좋은 문제같다.