题解：P13461 [GCJ 2008 #1B] Number Sets

· · 题解

本题解来自于《挑战程序设计竞赛》。

首先因为这是一个集合合并的问题，所以貌似可以使用并查集求解。如果对区间内的任意两个数查询是否包含不小于 P 的公共质因数，每一次查询由于需要分解质因数所以需要花费 O(\sqrt{B}) 的时间。因此，整个算法的时间复杂度就是 O((B - A)^2 \sqrt{B}) 。虽然可以通过 Small 数据，但是无法通过 Large 数据。

我们注意到 Large 有一个限制条件是 B - A \leq 1000000 。如果满足 A \leq a \leq b \leq B 的整数 a ， b 有公共质因数 p ，那么 p 一定能整除 b - a 。由于 B - A \leq 1000000 ，因此 p 也不会超过 1000000 。

当 a 和 b 有公共质因数 p 时， a 和 b 都是 p 的倍数。因此，不需要尝试 [A, B] 中所有的数对，只需要遍历所有可能的质因数 p ，对每一个 p 合并其所有倍数，就可以更加高效地求得答案。在合并时，从不小于 A 的最小的 p 的倍数 ((A + p - 1) / p \times p) 开始，不断枚举 p 的倍数直到不超过 B 的最大的 p 的倍数 (B / p \times p) ，并把这些数所在的集合合并起来。结合之前对区间筛法和并查集复杂度的分析，可以得出的整个算法的复杂度是 O(B - A) 。

typedef long long ll;

int prime[1000000]; // 不超过1000000的第i个的素数
int p;              // 素数的个数

// 输入
ll A, B, P;

void solve() {
    int len = B - A + 1;
    init_union_find(len); // 初始化并查集

    for (int i = 0; i < p; i++) {
        // 对不小于P的素数进行处理
        if (prime[i] >= P) {
            // 不小于A的最小的prime[i]的倍数
            ll start = (A + prime[i] - 1) / prime[i] * prime[i];
            // 不大于B的最大的prime[i]的倍数
            ll end = B / prime[i] * prime[i];

            for (ll j = start; j <= end; j += prime[i]) {
                // start和j属于同一个集合
                unite(start - A, j - A);
            }
        }
    }

    int res = 0;
    for (ll i = A; i <= B; i++) {
        // find(i) == i时，i就是并查集的根
        // 集合的个数等于根的个数
        if (find(i - A) == i - A) res++;
    }
    printf("%d\n", res);
}