CF1775D Friendly Spiders 题解

· · 题解

前言：翻了一下题解区，基本都是用质因子作为点建图的，其实可以直接拿给定的 a 数组建图。

首先预处理出每一个 a_i 的因子（除了 1 ），然后预处理出对于每个小于等于 a 数组最大值的正整数，哪些编号 i 满足 a_i 是它的倍数。

这一步分解 a_i 质因子时可以做完，复杂度 O(n \sqrt{a_i}) 。

代码中上述 2 个预处理结果分别保存在 p 和 q 中。

我们从 s 开始跑最短路，遍历 p[s] ，当前遍历到的元素记为 x ，如果 x 在之前遍历过了，忽略这个 x ，否则遍历 q[x] ，对其中的每一个元素进行更新，加入队列，继续这样操作。

注意到上面的思路基本就是暴力的最短路，关键就在于加粗的一行。我们发现如果 \gcd(x, y) = t 且 \gcd(y, z) = t ，那么 \gcd(x, z) \neq 1 （或者说 \gcd(x, z) \ge t ），所以说如果 x 先通过 \gcd(x, y) = t 到了 y ，再通过 \gcd(y, z) = t 到了 z ，完全可以直接从 x 到 z 。

这时候可能有的读者发现了，你这只是共用了中间 y 的情况啊，所以我们来讨论下一种情况：如果 \gcd(x, y) = t 且 \gcd(i, j) = t ，其中 y 通过若干条边到了 i （在没用上面加粗那行方法的前提下），同样的 \gcd(x, i) \ge t 且 \gcd(x, j) \ge t ，完全可以直接从 x 到 i 和 j 。

所以我们证明了可以使用上面那种做法保证正确性。

分析复杂度：边数即为 q 的大小，即为所有 a_i 的因数个数之和，因数个数最多就算 \sqrt{a_i} ，总共 n \sqrt{a_i} ，因为是 bfs ，所以复杂度 O(n \sqrt{a_i}) ，结合前面的预处理总复杂度为 O(n \sqrt{a_i}) ，在 2s 的情况下 3e5 跑根号绰绰有余。

code （代码极短，只有 1.1k ）：

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, a[N], s, t, d[N], pre[N];
bool vis[N];
vector<int> p[N], q[N];
queue<int> qu;
stack<int> pu;
void print(int x) {
    while (x != s) { pu.push(x); x = pre[x]; }
    cout << s << " ";
    while (!pu.empty()) { cout << pu.top() << " "; pu.pop(); }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    scanf("%d%d", &s, &t);
    for (int i = 1; i <= n; i++) {
        if (a[i] != 1) {
            p[i].push_back(a[i]);
            q[a[i]].push_back(i);
        }
        for (int j = 2; j * j <= a[i]; j++) {
            if (a[i] % j == 0) {
                p[i].push_back(j);
                p[i].push_back(a[i] / j);
                q[j].push_back(i);
                q[a[i] / j].push_back(i);
            }
        }       
    }
    qu.push(s); d[s] = 1;
    while (!qu.empty()) {
        int x = qu.front(); qu.pop();
        for (int i = 0; i < p[x].size(); i++) {
            int y = p[x][i];
            if (vis[y]) continue; vis[y] = 1;
            for (int j = 0; j < q[y].size(); j++) {
                int z = q[y][j];
                if (d[z] == 0) {
                    d[z] = d[x] + 1; qu.push(z); pre[z] = x;
                }
            }   
        }

    }
    if (d[t] == 0) puts("-1");
    else {
        cout << d[t] << endl;
        print(t);
    }
}