문제 개요

주어진 배열에서 구간 곱과 그 결과에 대한 오일러 피 함수 값을 계산하는 문제입니다. 핵심 아이디어는 오일러 피 함수의 성질과 300 이하의 소수가 62개뿐이라는 점을 활용하는 것입니다.

수학적 배경

구간 [l, r]의 곱을 X라고 할 때, X를 소인수분해하면 다음과 같습니다:

X = ∏ p_i^{c_i}   (i = 1 to n)

오일러 피 함수는 곱셈적 함수이므로:

φ(X) = φ(∏ p_i^{c_i})
     = ∏ φ(p_i^{c_i})
     = ∏ p_i^{c_i} × (p_i - 1) / p_i
     = X × ∏ (p_i - 1) / p_i

따라서 구간 곱 X와 각 소수의 존재 여부만 알면 φ(X)를 계산할 수 있습니다.

알고리즘 설계

세그먼트 트리를 사용하여 구간 곱과 소수 플래그를 관리합니다. 각 노드는 다음 정보를 저장합니다:

• mul: 구간의 곱 (mod 1e9+7)
• prime_flag: 62비트 정수 또는 비트셋으로 각 소수의 존재 여부

소수 집합은 300 이하의 62개 소수로 제한되므로, 비트 연산으로 효율적으로 처리할 수 있습니다.

세그먼트 트리 구현

트리 노드 구조

struct Node {
    int l, r;
    long long mul;
    long long prime_flag;
    long long lazy_mul;
    long long lazy_prime;
};

초기화 과정

void init() {
    // 에라토스테네스의 체로 300 이하 소수 찾기
    for (int i = 2; i <= 300; i++) prime[i] = 1;
    for (int i = 2; i * i <= 300; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= 300; j += i) {
                prime[j] = 0;
            }
        }
    }
    // 소수 리스트 생성
    for (int i = 2; i <= 300; i++) {
        if (prime[i]) primes[cnt++] = i;
    }
    // 역원 미리 계산
    for (int i = 0; i < cnt; i++) {
        inv[i] = modpow(primes[i], MOD - 2);
    }
}

트리 구축

void build(int node, int left, int right) {
    seg[node].l = left;
    seg[node].r = right;
    seg[node].lazy_mul = 1;
    seg[node].lazy_prime = 0;
    
    if (left == right) {
        scanf("%lld", &seg[node].mul);
        int val = seg[node].mul;
        for (int i = 0; i < cnt; i++) {
            if (val % primes[i] == 0) {
                seg[node].prime_flag |= (1LL << i);
            }
        }
        return;
    }
    int mid = (left + right) >> 1;
    build(node * 2, left, mid);
    build(node * 2 + 1, mid + 1, right);
    push_up(node);
}

업데이트 연산

void update(int node, int left, int right, int val) {
    if (seg[node].l == left && seg[node].r == right) {
        // 구간 곱 업데이트
        seg[node].mul = seg[node].mul * modpow(val, seg[node].r - seg[node].l + 1) % MOD;
        seg[node].lazy_mul = seg[node].lazy_mul * val % MOD;
        // 소수 플래그 업데이트
        for (int i = 0; i < cnt; i++) {
            if (val % primes[i] == 0) {
                seg[node].prime_flag |= (1LL << i);
                seg[node].lazy_prime |= (1LL << i);
            }
        }
        return;
    }
    push_down(node);
    int mid = (seg[node].l + seg[node].r) >> 1;
    if (right <= mid) update(node * 2, left, right, val);
    else if (left > mid) update(node * 2 + 1, left, right, val);
    else {
        update(node * 2, left, mid, val);
        update(node * 2 + 1, mid + 1, right, val);
    }
    push_up(node);
}

쿼리 처리

pair<long long, long long> query(int node, int left, int right) {
    if (seg[node].l == left && seg[node].r == right) {
        return {seg[node].mul, seg[node].prime_flag};
    }
    push_down(node);
    int mid = (seg[node].l + seg[node].r) >> 1;
    if (right <= mid) return query(node * 2, left, right);
    if (left > mid) return query(node * 2 + 1, left, right);
    auto left_res = query(node * 2, left, mid);
    auto right_res = query(node * 2 + 1, mid + 1, right);
    return {
        left_res.first * right_res.first % MOD,
        left_res.second | right_res.second
    };
}

최종 결과 계산

void process_query(int l, int r) {
    auto result = query(1, l, r);
    long long ans = result.first;
    long long prime_mask = result.second;
    
    for (int i = 0; i < cnt; i++) {
        if (prime_mask & (1LL << i)) {
            ans = ans * (primes[i] - 1) % MOD * inv[i] % MOD;
        }
    }
    printf("%lld\n", ans);
}

Bitset 버전의 장점

비트셋을 사용하면 코드가 더 간결해지고 메모리 사용량이 줄어듭니다. 62비트만 필요하므로 std::bitset을 사용하여 가독성을 높일 수 있습니다. 주요 변경점은 다음과 같습니다:

• 비트 연산 대신 bitset::set(), bitset::reset(), bitset::operator|= 사용
• 비트셋의 크기가 명시적으로 표현되어 가독성 향상
• 메모리 사용량 최적화

시간 복잡도

모든 연산은 O((N+Q) log N × 62) 시간에 수행됩니다. 62개의 소수를 확인하는 상수 시간이 추가되지만, 문제의 제약 조건인 N, Q ≤ 10^5에서 충분히 효율적입니다.