大家的公因数 2

预期难度：铜+/银（蓝）
关键词：筛法、质因数分解、图、线性基

由题意可知，两个点有一个大于 1 的公因数时会连边，则我们可以枚举每个数对的因数，根据因数的情况进行连边。

这样建图的复杂度为

\mathcal O(n^2 \sqrt a_i)

的，不能接受。

考虑不枚举数对，可以通过并查集维护每个数对应的连通块，在同一个连通块

i

中的数至少都有公因数

i

。

暴力枚举每个数的因数时复杂度为

\mathcal O(n \sqrt a_i)

，本数据范围无法通过，对每个数进行质因数分解即可。

不需要显式建图，只需要记录下每个连通块中有哪些点即可。

对于查询

(u_i, v_i, w_i)

，进行分类讨论：

若 $u_i$ 和 $v_i$ 不在同一个连通块，必然无法找到合法的路径；
若 $u_i$ 和 $v_i$ 在同一个连通块，由样例解释可知，我们可以经过同一个点两次，从而消除该点对异或和的影响。因此，问题转化为，给定若干数，能否从其中选出一些数使得其异或和为 $w_i$ 。线性基即可解决。

时间复杂度为

\mathcal O\left(n \sqrt{\frac{a_i}{\ln a_i}} + q \log n\right)

。

CPP

#include<bits/stdc++.h>
#define endl '\n'
#define ioclear std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
 
using i64 = long long;
 
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if(siz[x] > siz[y])
            std::swap(x, y);
        assert(siz[x] <= siz[y]);
        siz[y] += siz[x];
        f[x] = y;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};
 
struct Basis
{
    using i64 = long long;
    using T = i64;
    static const int n = 60;
 
    T p[n + 10] {};
 
    void add(T x)
    {
        for(int i = n; i >= 0; i--)
            if(x >> i & 1)
            {
                if(p[i] == 0)
                {
                    p[i] = x;
                    break;
                }
                x ^= p[i];
            }
        return;
    }
 
    bool query(T x)
    {
        for(int i = n; i >= 0; i--)
            if((x >> i & 1) && p[i] != 0)
                x ^= p[i];
        return x == 0;
    }
    
    T mx()
    {
        T ans = 0;
        for(int i = n; i >= 0; i--)
            ans = std::max(ans, (ans ^ p[i]));
        return ans;
    }
};
 
std::vector<int> primes;
 
void init(int up)
{
    std::vector<int> vis(up + 1, 0);
    for(int i = 2; i <= up; i++)
    {
        if(!vis[i])
        {
            primes.push_back(i);
            for(int j = 2; i * j <= up; j++)
                vis[i * j] = 1;
        }
    }
    return;
}
 
void solve()
{
    int n, mx = 0;
    std::cin >> n;
    std::vector<int> a(n + 1);
    std::vector<i64> p(n + 1);
    for(int i = 1; i <= n; i++)
    {
        std::cin >> a[i];
        mx = std::max(mx, a[i]);
    } 
    for(int i = 1; i <= n; i++)
        std::cin >> p[i];
    DSU dsu(mx + 1);
    for(int i = 1; i <= n; i++)
    {
        auto cur = a[i];
        for(auto v: primes)
        {
            if(v * v > cur)
                break;
            if(cur % v == 0)
            {
                dsu.merge(a[i], v);
                while(cur % v == 0)
                    cur /= v;
            }
        }
        if(cur > 1)
            dsu.merge(a[i], cur);
    }
    std::map<int, Basis> basis;
    // std::vector<Basis<i64>> basis(mx + 1, Basis<i64>(60));
    for(int i = 1; i <= n; i++)
        basis[dsu.find(a[i])].add(p[i]);
    int q;
    std::cin >> q;
    while(q--)
    {
        int u, v;
        i64 w;
        std::cin >> u >> v >> w;
        if(dsu.find(u) != dsu.find(v))
        {
            std::cout << "No\n";
            continue;
        }
        if(basis[dsu.find(u)].query(w))
            std::cout << "Yes\n";
        else
            std::cout << "No\n";
    }
}
 
int main()
{
    #ifdef ONLINE_JUDGE
    ioclear;
    #endif
 
    init(1E7 + 10);
    int t = 1;
    // std::cin >> t;
    while(t--)
        solve();
}

题解：P11867 大家的公因数 2

文章操作

大家的公因数 2

相关推荐

评论

题解：P11867 大家的公因数 2