문제 분석 및 접근

주어진 데이터 크기를 고려하면 사전에 연산을 수행하는 전처리 과정이 필수적이며, 각 질의는 O(log N) 이하의 시간 복잡도로 처리해야 합니다. 함수 F(x)를 x의 서로 다른 소인수의 개수라고 할 때, 입력의 최댓값이 1,000,000이므로 1 ≤ F(x) ≤ 7의 범위를 가짐을 수학적으로 유도할 수 있습니다. 따라서 임의의 구간 [L, R]에 대해 F(x) 값이 1부터 7까지 각각 몇 개씩 존재하는지 파악하고, 그중 최대공약수(GCD)가 가장 크게 되는 조합을 찾으면 됩니다.

빈도수를 기록하기 위해 1부터 7까지의 개수를 저장하는 구조체를 정의합니다. 이 구조체는 덧셈과 뺄셈 연산을 지원하므로, 누적합 배열을 구성하여 구간 [L, R]의 빈도수를 O(1)에 구할 수 있습니다. 구간 내 빈도수를 알아낸 후에는 1부터 7까지의 모든 쌍에 대해 최대공약수를 계산하여 정답을 갱신합니다. 동일한 값이 2개 이상 존재한다면 해당 값 자체가 최대공약수가 될 수 있음에 유의해야 합니다.

누적합을 활용한 구현

먼저 에라토스테네스의 체를 변형하여 각 수의 소인수 개수를 계산하고, 이를 바탕으로 구조체의 누적합을 구축하는 방식입니다.

#include <cstdio>
#include <cstring>

const int MAX_N = 1000005;

struct FreqInfo {
    int cnt[8];
    FreqInfo() { memset(cnt, 0, sizeof(cnt)); }
    FreqInfo operator+(const FreqInfo& rhs) const {
        FreqInfo res;
        for (int i = 1; i <= 7; ++i) res.cnt[i] = cnt[i] + rhs.cnt[i];
        return res;
    }
    FreqInfo operator-(const FreqInfo& rhs) const {
        FreqInfo res;
        for (int i = 1; i <= 7; ++i) res.cnt[i] = cnt[i] - rhs.cnt[i];
        return res;
    }
};

int prime_cnt[MAX_N];
FreqInfo pref[MAX_N];

void preprocess() {
    for (int i = 2; i < MAX_N; ++i) {
        if (prime_cnt[i] == 0) {
            for (int j = i; j < MAX_N; j += i) {
                prime_cnt[j]++;
            }
        }
    }
    for (int i = 2; i < MAX_N; ++i) {
        pref[i] = pref[i - 1];
        pref[i].cnt[prime_cnt[i]]++;
    }
}

int getGcd(int a, int b) {
    return b == 0 ? a : getGcd(b, a % b);
}

int main() {
    preprocess();
    int t;
    scanf("%d", &t);
    while (t--) {
        int l, r;
        scanf("%d %d", &l, &r);
        FreqInfo range_freq = pref[r] - pref[l - 1];
        int max_gcd = 0;
        for (int i = 1; i <= 7; ++i) {
            if (range_freq.cnt[i] >= 2) {
                max_gcd = (max_gcd > i) ? max_gcd : i;
            }
            for (int j = i + 1; j <= 7; ++j) {
                if (range_freq.cnt[i] > 0 && range_freq.cnt[j] > 0) {
                    int g = getGcd(i, j);
                    max_gcd = (max_gcd > g) ? max_gcd : g;
                }
            }
        }
        printf("%d\n", max_gcd);
    }
    return 0;
}

펜윅 트리(Fenwick Tree)를 활용한 구현

누적합을 동적으로 유지하고 쿼리해야 하는 상황을 떠올리면 펜윅 트리를 떠올릴 수 있습니다. 펜윅 트리는 단순히 int나 long long 같은 기본 자료형뿐만 아니라, 덧셈과 뺄셈 연산이 정의된 구조체라면 어떤 형태든 유연하게 관리할 수 있습니다. 이를 템플릿 클래스로 구현하면 다음과 같습니다.

#include <cstdio>
#include <cstring>

const int MAX_N = 1000005;

struct FreqInfo {
    int cnt[8];
    FreqInfo() { memset(cnt, 0, sizeof(cnt)); }
    FreqInfo operator+(const FreqInfo& rhs) const {
        FreqInfo res;
        for (int i = 1; i <= 7; ++i) res.cnt[i] = cnt[i] + rhs.cnt[i];
        return res;
    }
    FreqInfo operator-(const FreqInfo& rhs) const {
        FreqInfo res;
        for (int i = 1; i <= 7; ++i) res.cnt[i] = cnt[i] - rhs.cnt[i];
        return res;
    }
};

int prime_cnt[MAX_N];
FreqInfo bit[MAX_N];

int lowbit(int x) { return x & (-x); }

void add(int idx, const FreqInfo& val) {
    while (idx < MAX_N) {
        bit[idx] = bit[idx] + val;
        idx += lowbit(idx);
    }
}

FreqInfo query(int idx) {
    FreqInfo res;
    while (idx > 0) {
        res = res + bit[idx];
        idx -= lowbit(idx);
    }
    return res;
}

void preprocess() {
    for (int i = 2; i < MAX_N; ++i) {
        if (prime_cnt[i] == 0) {
            for (int j = i; j < MAX_N; j += i) {
                prime_cnt[j]++;
            }
        }
    }
    for (int i = 2; i < MAX_N; ++i) {
        FreqInfo tmp;
        tmp.cnt[prime_cnt[i]]++;
        add(i, tmp);
    }
}

int getGcd(int a, int b) {
    return b == 0 ? a : getGcd(b, a % b);
}

int main() {
    preprocess();
    int t;
    scanf("%d", &t);
    while (t--) {
        int l, r;
        scanf("%d %d", &l, &r);
        FreqInfo range_freq = query(r) - query(l - 1);
        int max_gcd = 0;
        for (int i = 1; i <= 7; ++i) {
            if (range_freq.cnt[i] >= 2) {
                max_gcd = (max_gcd > i) ? max_gcd : i;
            }
            for (int j = i + 1; j <= 7; ++j) {
                if (range_freq.cnt[i] > 0 && range_freq.cnt[j] > 0) {
                    int g = getGcd(i, j);
                    max_gcd = (max_gcd > g) ? max_gcd : g;
                }
            }
        }
        printf("%d\n", max_gcd);
    }
    return 0;
}