문제 개요

배열의 각 원소에 대해 오일러 함수를 반복적으로 적용하면서, 특정 범위 내의 모든 원소가 동일한 값으로 수렴하는 최소 연산 횟수를 구하는 문제입니다. 이 과정에서 선형 시간 전처리와 세그먼트 트리, 그리고 LCA(Lowest Common Ancestor) 기법을 결합하여 효율적인 쿼리를 처리합니다.

핵심 아이디어

• 오일러 함수 φ(n)는 정수 n에 대해 1부터 n까지의 자연수 중 n과 서로소인 수의 개수를 의미합니다.
• 임의의 수 n에 대해 φ(φ(...φ(n)))를 반복 적용하면 결국 1이 되며, 이 과정의 최대 반복 횟수는 약 23회에 불과합니다 (5×10⁶ 범위 내).
• 따라서 각 원소에 대한 연산은 고작 23번 이내로 제한되며, 전체 배열에 대한 처리도 상수 시간 복잡도로 가능합니다.

전처리: 오일러 함수 계산

선형 소수 여부 판별을 통해 오일러 함수를 미리 계산합니다. 에라토스테네스의 체 방식으로 phi[i] 값을 계산하고, 이를 기반으로 깊이 정보 dep[i]를 설정합니다.

void precompute_phi() {
    for (int i = 1; i <= MAXN; ++i) is_prime[i] = true;
    is_prime[1] = false;
    phi[1] = 1;
    int cnt = 0;
    for (int i = 2; i <= MAXN; ++i) {
        if (is_prime[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= MAXN; ++j) {
            is_prime[i * prime[j]] = false;
            if (i % prime[j]) {
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            } else {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}

깊이 및 부모 정보 초기화

각 숫자 i의 부모는 phi[i]이며, 이를 기반으로 트리 구조를 형성합니다. 이후 이 트리에서 두 노드의 최저 공통 조상(LCA)을 빠르게 찾기 위해 이중 배열 fa[u][k]를 사용해 이진 상승 기법을 적용합니다.

void init_lca(int n) {
    for (int k = 1; k < 6; ++k)
        for (int u = 1; u <= n; ++u)
            fa[u][k] = fa[fa[u][k-1]][k-1];
}

int get_lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int k = 5; k >= 0; --k)
        if (dep[u] - dep[v] >= (1 << k))
            u = fa[u][k];
    if (u == v) return u;
    for (int k = 5; k >= 0; --k)
        if (fa[u][k] != fa[v][k])
            u = fa[u][k], v = fa[v][k];
    return fa[u][0];
}

세그먼트 트리 설계

세그먼트 트리의 각 노드는 다음과 같은 정보를 저장합니다:

• lca: 해당 구간 내 모든 원소의 최저 공통 조상
• cnt: 구간 내 원소 개수
• ans: 구간 내 모든 원소가 공통 조상으로 모일 때 필요한 거리 합

push_up 연산에서는 자식 구간의 결과를 기반으로 현재 노드의 ans를 업데이트합니다. 이때, 자식의 lca에서 현재 노드의 lca까지의 거리에 해당 구간의 원소 수를 곱해 누적합니다.

void push_up(int p) {
    cnt[p] = cnt[p<<1] + cnt[p<<1|1];
    lca[p] = get_lca(lca[p<<1], lca[p<<1|1]);
    ans[p] = (dep[lca[p<<1]] - dep[lca[p]]) * cnt[p<<1]
           + (dep[lca[p<<1|1]] - dep[lca[p]]) * cnt[p<<1|1]
           + ans[p<<1] + ans[p<<1|1];
}

쿼리 및 업데이트 처리

업데이트 쿼리(op=1)는 구간 내 모든 원소에 대해 오일러 함수를 한 번 적용합니다. 만약 값이 1이면 더 이상 변경하지 않으며, 그렇지 않으면 부모로 이동합니다.

질의 쿼리(op=2)는 주어진 구간에서 모든 원소가 공통 조상으로 수렴하는 최소 거리 합을 반환합니다. 이는 세그먼트 트리의 query 함수를 통해 재귀적으로 합산됩니다.

void update(int p, int l, int r, int ql, int qr) {
    if (!sum[p]) return;
    if (l == r) {
        sum[p]--;
        lca[p] = fa[lca[p]][0];
        return;
    }
    int mid = (l + r) / 2;
    if (ql <= mid) update(p<<1, l, mid, ql, qr);
    if (mid < qr) update(p<<1|1, mid+1, r, ql, qr);
    push_up(p);
}

node query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return {lca[p], cnt[p], ans[p]};
    node left = {0,0,0}, right = {0,0,0};
    int mid = (l + r) / 2;
    if (ql <= mid) left = query(p<<1, l, mid, ql, qr);
    if (mid < qr) right = query(p<<1|1, mid+1, r, ql, qr);
    node res;
    res.lca = get_lca(left.lca, right.lca);
    res.cnt = left.cnt + right.cnt;
    res.ans = left.ans + right.ans;
    if (left.lca) res.ans += left.cnt * (dep[left.lca] - dep[res.lca]);
    if (right.lca) res.ans += right.cnt * (dep[right.lca] - dep[res.lca]);
    return res;
}

결론

이 접근법은 오일러 함수의 특성과 트리 구조를 활용해, 매번 모든 원소를 직접 수정하지 않고도 효과적으로 상태를 갱신할 수 있도록 합니다. 세그먼트 트리의 빠른 집계와 LCA 기반의 거리 계산이 결합되어, 대규모 쿼리에서도 빠른 응답이 가능합니다.