약수 관계를 가진 정수 삼원조의 개수 구하기

양의 정수 \(n\)이 주어졌을 때, 다음의 조건을 모두 만족하는 정수 삼원조 \((a, b, c)\)의 개수를 구하는 문제입니다.

• \(a + b + c = n\)
• \(1 \le a < b < c \le n\)
• \(a\)는 \(b\)의 약수이고, \(b\)는 \(c\)의 약수이다.

이 문제의 핵심은 약수 관계를 매개변수로 치환하여 식을 단순화하는 것입니다. \(b = k_1 \cdot a\), \(c = k_2 \cdot b = k_1 \cdot k_2 \cdot a\)라고 정의하면 (\(k_1, k_2 > 1\)), 합의 공식은 다음과 같이 변형됩니다.

\[a(1 + k_1 + k_1 \cdot k_2) = n\]

우선 \(a\)는 \(n\)의 약수여야 합니다. \(n\)의 모든 약수를 순회하며 각 \(a\)에 대해 다음 식을 만족하는 \(k_1, k_2\)를 찾습니다.

\[k_1(1 + k_2) = \frac{n}{a} - 1\]

이제 \(M = \frac{n}{a} - 1\)이라 할 때, \(k_1\)은 \(M\)의 약수여야 합니다. \(M\)의 약수를 모두 탐색하면서 \(k_1 > 1\)이고 \(k_2 = \frac{M}{k_1} - 1 > 1\)인 경우를 카운트합니다. 이 알고리즘은 \(10^9\) 범위의 입력에 대해 약수의 개수가 상대적으로 적으므로 충분히 시간 내에 동작합니다.

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ll target_n;
    cin >> target_n;

    ll total_triplets = 0;
    for (ll val_a = 1; val_a * 3 < target_n; ++val_a) {
        if (target_n % val_a != 0) continue;

        ll remaining = target_n / val_a - 1;
        for (ll factor = 1; factor * factor <= remaining; ++factor) {
            if (remaining % factor == 0) {
                // Case 1: k1 = factor
                ll k1 = factor;
                ll k2 = (remaining / factor) - 1;
                if (k1 > 1 && k2 > 1) total_triplets++;

                // Case 2: k1 = remaining / factor
                if (factor * factor != remaining) {
                    ll k1_alt = remaining / factor;
                    ll k2_alt = factor - 1;
                    if (k1_alt > 1 && k2_alt > 1) total_triplets++;
                }
            }
        }
    }
    cout << total_triplets;
    return 0;
}

이차원 평면 위 직사각형 가중치의 총합 계산

\(N \times N\) 격자 평면 위에 \(n\)개의 흑백 점이 존재합니다. 임의의 직사각형 내부에 포함된 검은 점의 개수와 흰 점의 개수의 곱을 해당 직사각형의 가중치로 정의할 때, 가능한 모든 직사각형 가중치의 합을 \(2^{64}\)로 나눈 나머지를 구해야 합니다.

이 문제는 모든 직사각형을 순회하는 대신, 검은 점 하나와 흰 점 하나를 선택했을 때 두 점을 동시에 포함하는 직사각형의 개수를 합산하는 방식으로 전환할 수 있습니다. 점 \(P_1(x_1, y_1)\)과 \(P_2(x_2, y_2)\)를 포함하는 직사각형의 개수는 다음과 같습니다.

\[ \min(x_1, x_2) \times (N - \max(x_1, x_2) + 1) \times \min(y_1, y_2) \times (N - \max(y_1, y_2) + 1) \]

스위핑(Sweep-line) 기법과 펜윅 트리(Fenwick Tree)를 사용하여 \(O(n \log n)\)에 해결할 수 있습니다. \(x\) 좌표를 기준으로 점들을 정렬한 뒤, 현재 점과 이전에 처리된 서로 다른 색상의 점들 사이의 관계를 펜윅 트리에 기록하며 계산합니다. 이때 \(y\) 좌표에 대한 구간 합을 구하기 위해 좌표 이산화가 필요합니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned long long ull;

struct Point {
    long long px, py;
    int color;
};

struct FenwickTree {
    vector<ull> tree;
    int size;
    FenwickTree(int n) : size(n), tree(n + 1, 0) {}
    void add(int i, ull val) {
        for (; i <= size; i += i & -i) tree[i] += val;
    }
    ull query(int i) {
        ull res = 0;
        for (; i > 0; i -= i & -i) res += tree[i];
        return res;
    }
};

int main() {
    int n;
    long long max_coord;
    cin >> n >> max_coord;

    vector<Point> pts(n);
    vector<long long> y_coords;
    for (int i = 0; i < n; ++i) {
        cin >> pts[i].px >> pts[i].py >> pts[i].color;
        y_coords.push_back(pts[i].py);
    }

    sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        return a.px < b.px;
    });
    sort(y_coords.begin(), y_coords.end());
    y_coords.erase(unique(y_coords.begin(), y_coords.end()), y_coords.end());

    int m = y_coords.size();
    FenwickTree ft[2][2] = {FenwickTree(m), FenwickTree(m), FenwickTree(m), FenwickTree(m)};
    ull total_ans = 0;

    for (int i = 0; i < n; ++i) {
        int y_idx = lower_bound(y_coords.begin(), y_coords.end(), pts[i].py) - y_coords.begin() + 1;
        int c = pts[i].color;
        int opp = 1 - c;

        ull weight_x = (ull)(max_coord - pts[i].px + 1);
        ull weight_y_high = (ull)(max_coord - pts[i].py + 1);
        ull weight_y_low = (ull)pts[i].py;

        total_ans += weight_x * weight_y_high * ft[opp][0].query(y_idx - 1);
        total_ans += weight_x * weight_y_low * (ft[opp][1].query(m) - ft[opp][1].query(y_idx - 1));

        ft[c][0].add(y_idx, (ull)pts[i].px * pts[i].py);
        ft[c][1].add(y_idx, (ull)pts[i].px * (max_coord - pts[i].py + 1));
    }

    cout << total_ans << endl;
    return 0;
}

구간 절단 시뮬레이션과 세그먼트 트리

\(n\)개의 구간 \([l_i, r_i]\)가 있고, \(m\)번의 절단 작업이 주어집니다. 각 작업은 위치 \(x\)에서 지정된 범위의 구간들을 절단하며, 절단 후 더 긴 쪽을 남깁니다. 만약 길이가 같다면 왼쪽을 남깁니다.

단순 시뮬레이션은 \(O(nm)\)의 복잡도를 가지지만, 절단 위치 \(x\)가 무작위 순열이거나 특정 조건이 붙는 경우 기댓값 관점에서 구간의 길이가 빠르게 줄어듭니다. 하지만 최악의 경우를 대비해 세그먼트 트리를 활용한 최적화가 필요합니다.

구간의 최소값을 빠르게 찾기 위해 세그먼트 트리를 구축하고, 각 절단 작업의 시간 순서를 인덱싱하여 관리합니다. 특정 구간 내에서 가장 먼저 발생하는 절단 작업을 찾아 이진 탐색 기법으로 구간을 갱신하는 방식으로 접근할 수 있습니다. 각 구간은 최대 \(O(\log m)\)번 유의미하게 절단되므로 효율적인 처리가 가능합니다.

그래프 생성 공정에서의 확률 계산

\(n\)개의 정점이 있는 그래프에서 고립된 정점(차수가 0인 정점)이 하나라도 포함된 쌍을 선택해 간선을 추가하는 과정을 반복합니다. 모든 정점의 차수가 1 이상이 되어 더 이상 간선을 추가할 수 없을 때까지의 과정 중, 정확히 \(m\)번의 작업 후에 멈출 확률을 계산하는 문제입니다.

이 문제는 조합론적 관점에서 접근해야 하며, 정점들이 고립 상태를 벗어나는 시점의 상태 전이를 동적 계획법(DP)이나 포함-배제 원리로 모델링할 수 있습니다. 특히 \(n\)의 범위가 \(10^7\)로 매우 크기 때문에 선형 시간 복잡도 내에 수식을 정리하여 계산하는 것이 관건입니다.