P1621 集合

Link

题解

套着并查集的数学题，先用线性筛得到[p, r]范围内的素数，再在[l, r]范围内枚举[p, r]中每个素数的倍数，并将这些倍数加入并查集，最后输出并查集连通分量的个数。

[l, r]中每个属于[p, r]的素数的倍数的公共质因数一定大于等于p，也就是说每个素数的倍数们一定属于同一集合。

代码

#include <algorithm>
#include <cmath>
#include <iostream>

#define LL long long

const double pi = 3.14;
const int maxn = 100010;

int prime[maxn + 10], not_pr[maxn + 10], primelr[maxn + 10];

void get_list() {
    int tot = 0;
    for (int i = 2; i <= maxn; i++) {
        if (!not_pr[i]) prime[++tot] = i;
        for (int j = 1; j <= tot && i * prime[j] <= maxn; j++) {
            not_pr[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

class DS {
private:
    int rt[maxn];

public:
    int count;  // 连通分量的个数
    DS(int n) {
        count = n;
        for (size_t i = 1; i <= n; i++) rt[i] = i;
    }

    int find_rt(int x) {
        if (rt[x] == x) return x;
        else return rt[x] = find_rt(rt[x]);
    }

    void merge(int x, int y) {
        int xrt = find_rt(x);
        int yrt = find_rt(y);
        if (xrt != yrt) {
            rt[xrt] = yrt;
            count--;
        }
    }

    bool is_connected(int x, int y) { return find_rt(x) == find_rt(y); }
};

int main() {
    int l, r, p;
    get_list();  // 线性筛
    while (std::cin >> l >> r >> p) {
        DS ds = DS(r);
        int idx = 0;
        for (int i = p; i <= r; i++)
            if (!not_pr[i]) primelr[++idx] = i;
        for (int i = 1; i <= idx; i++) {
            int k = 1;
            while (k * primelr[i] < l) k++;
            while (primelr[i] * ++k <= r) ds.merge(primelr[i] * (k - 1), primelr[i] * k);
        }
        std::cout << ds.count - l + 1 << std::endl;
    }
    return 0;
}