G. Phoenix and Odometers - 题解

比赛与标签

比赛: Codeforces Global Round 14 标签: dfs and similar, graphs, math, number theory 难度: *2700

喵喵大意 ~ 题目讲了什么呀？

主人你好呀~！这道题是说，在一个由 n 个交叉口和 m 条单向道路组成的火之城里，每条路都有自己的长度。

我们有 q 辆车车，每辆车都有一个神奇的里程表。第 i 辆车从 v_i 路口出发，里程表初始读数是 s_i，每开一英里数字就加一，当读数达到 t_i 时就会立刻归零。

我们的任务是，对于每一辆车，判断 Phoenix 能不能驾驶它从起点出发，在城里转悠一圈（或者好几圈），最后回到起点，并且让里程表的读数正好变回 0 呢？如果可以的话就告诉 Phoenix "YES"，不然就说 "NO"，喵~

简单来说，对于每个查询 (v, s, t)，我们要判断是否存在一条从 v 出发最终又回到 v 的路径，其总长度设为 L，能满足 (s + L) % t == 0 这个条件哦。

解题思路大冒险！

这道题看起来有点复杂，把图论和数论结合在了一起，但是别怕，我们一步一步来拆解它，就像猫猫拆毛线团一样，很快就能找到线头的说！

第一步：回到起点意味着什么？

一个非常重要的观察是，要想从一个点 v 出发，经过一些路，最后还能回到 v，那么整个行驶过程必须在一个强连通分量 (Strongly Connected Component, SCC) 内完成！因为在 SCC 里面，任何两个点都是互相可达的。如果一条路把你带出了所在的 SCC，你就再也回不来啦，喵~

所以，对于每个查询 (v, s, t)，我们只关心 v 所在的那个 SCC。

第二步：里程表的秘密

我们的目标是让最终里程表读数为 0，也就是 (s + L) % t == 0。这其实是一个同余方程，它告诉我们 s + L 必须是 t 的整数倍。

那么，我们能走出的路径总长度 L 都有哪些可能性呢？

在一个 SCC 内部，如果我们从 v 出发回到 v，可以走一个简单的环，也可以走很多个环，或者同一个环走很多次。这启发我们，所有可能的路径长度 L 之间一定有某种数学关系！

第三步：寻找“万能公约数” g

让我们来深入探究一下 SCC 内的路径长度。假设在一个 SCC 中，我们从某个固定的起点出发，通过不同的路径到达了同一个点 u，这两条路径的长度分别是 P1 和 P2。那么，我们就可以通过走一条路再“倒着”走另一条路（概念上），构造出一个长度为 |P1 - P2| 的环。

这引出了一个超级关键的结论，喵！对于一个特定的 SCC，所有从任意点出发再回到该点的环路长度，都是某个特定值 g 的倍数！ 这个 g 就是这个 SCC 内所有“基本环路”长度的最大公约数 (GCD)。

那么，怎么求这个神奇的 g 呢？

我们可以在这个 SCC 内部做一次深度优先搜索（DFS）。
从 SCC 的任意一个点 start_node 开始，记录从 start_node 到其他点 u 的路径长度 dist[u]。
当我们从 u 遍历到一条边 (u, v)，长度为 l 时：
- 如果 v 还没访问过，我们就更新 dist[v] = dist[u] + l，然后继续访问 v。
- 如果 v 已经访问过了，说明我们找到了一个环！我们有两条从 start_node 到 v 的路径：一条是之前找到的，长度为 dist[v]；另一条是现在通过 u 过来的，长度为 dist[u] + l。这两条路径的长度差 abs((dist[u] + l) - dist[v]) 就是一个环路长度的差值。我们将这个差值和我们当前记录的 g 取一次 GCD。
遍历完 SCC 内所有的边之后，g 就是我们要求的那个“万能公约数”啦！

第四步：整合起来，解决问题！

现在我们把所有线索串起来：

对于一个查询 (v, s, t)，我们首先找到 v 所在的 SCC。
然后我们求出这个 SCC 的“万能公约数” g。
我们知道，所有可能的路径总长 L 都必须是 g 的倍数，即 L = k * g（k 是非负整数）。
我们的目标是满足 (s + L) % t == 0，代入 L 就是 (s + k * g) % t == 0。
这个式子等价于 s + k * g 是 t 的倍数。写成方程就是 s + k * g = m * t，其中 m 是某个整数。
整理一下，得到 k * g - m * t = -s。这是一个关于 k 和 m 的线性丢番图方程！
根据裴蜀定理，这个方程有解的充要条件是 gcd(g, t) 能够整除 -s。因为 gcd 是正数，所以也就是 gcd(g, t) 能够整除 s。
所以，最后的判断条件就非常简单了：s % gcd(g, t) == 0。如果成立，答案就是 "YES"，否则就是 "NO"，搞定收工，喵~！

总结一下我们的完整算法:

使用 Tarjan 算法把整个图分解成若干个 SCC。
对每个 SCC，用一次 DFS 来计算出它的路径长度万能公约数 g。
对于每个查询 (v, s, t)，找到 v 对应的 SCC 的 g，然后检查 s % gcd(g, t) == 0 是否成立。

代码实现喵~

下面就是把我们的思路变成现实的代码啦，主人请看~ 我加了详细的注释，方便理解每一部分在做什么哦！

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

// 提升IO速度的小魔法~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

const int MAXN = 200005;
std::vector<std::pair<int, int>> adj[MAXN]; // 邻接表存图，边带权
int n, m, q;

// Tarjan 算法需要的变量们
int timer;
int ids[MAXN], low[MAXN]; // 发现时间和最低可追溯时间
bool onStack[MAXN];      // 节点是否在栈中
std::vector<int> st;     // Tarjan 用的栈
int scc_id[MAXN];        // 每个节点所属的 SCC 编号
int scc_count;           // SCC 的总数

// 计算 GCD 需要的变量们
long long scc_g[MAXN]; // 每个 SCC 的路径长度 GCD
long long dist[MAXN];  // DFS 中用来记录路径长度

// Tarjan 算法，用来找到所有的强连通分量 (SCC)
void tarjan_dfs(int u) {
    st.push_back(u);
    onStack[u] = true;
    ids[u] = low[u] = ++timer;

    for (auto& edge : adj[u]) {
        int v = edge.first;
        if (ids[v] == 0) { // 如果 v 还没被访问过
            tarjan_dfs(v);
            low[u] = std::min(low[u], low[v]);
        } else if (onStack[v]) { // 如果 v 在栈里，说明找到了一个环（返祖边）
            low[u] = std::min(low[u], ids[v]);
        }
    }

    // 如果 u 是一个 SCC 的根节点
    if (low[u] == ids[u]) {
        ++scc_count;
        while (true) {
            int node = st.back();
            st.pop_back();
            onStack[node] = false;
            scc_id[node] = scc_count; // 标记这个 SCC 的所有点
            if (node == u) break;
        }
    }
}

// DFS 来计算每个 SCC 的路径长度 GCD
void compute_gcd_dfs(int u, long long current_dist, int current_scc_id) {
    dist[u] = current_dist;
    for (auto& edge : adj[u]) {
        int v = edge.first;
        int l = edge.second;
        // 只在同一个 SCC 内部进行探索
        if (scc_id[v] == current_scc_id) {
            if (dist[v] == -1) { // 如果 v 在这个 SCC 中还没被访问过
                compute_gcd_dfs(v, current_dist + l, current_scc_id);
            } else { // 如果 v 已经被访问过了，说明我们找到了两条路径，可以计算路径差
                long long diff = std::abs((current_dist + l) - dist[v]);
                // 更新这个 SCC 的 GCD
                scc_g[current_scc_id] = std::gcd(scc_g[current_scc_id], diff);
            }
        }
    }
}

int main() {
    fast_io();

    std::cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, l;
        std::cin >> u >> v >> l;
        adj[u].push_back({v, l});
    }

    // 步骤 1: 用 Tarjan 算法找到所有 SCC
    for (int i = 1; i <= n; ++i) {
        if (ids[i] == 0) {
            tarjan_dfs(i);
        }
    }

    // 步骤 2: 为每个 SCC 计算路径长度的 GCD
    for (int i = 1; i <= n; ++i) {
        dist[i] = -1; // 重置 dist 数组，为下一次遍历做准备
    }
    for (int i = 1; i <= n; ++i) {
        if (dist[i] == -1) { // 从每个连通块（图论意义上的）的未访问节点开始
            compute_gcd_dfs(i, 0, scc_id[i]);
        }
    }

    // 步骤 3: 处理所有查询
    std::cin >> q;
    while (q--) {
        int v;
        long long s, t;
        std::cin >> v >> s >> t;
        
        // 获取 v 所在 SCC 的 GCD 值 g
        long long g = scc_g[scc_id[v]];
        
        // 我们的目标是找到一个 L = k*g (k>=0)，使得 (s+L)%t == 0
        // 这等价于 s + k*g 是 t 的倍数
        // 也就是 k*g - m*t = -s 这个丢番图方程有解
        // 有解的条件是 gcd(g, t) 能够整除 s
        
        // 注意：如果 g=0 (SCC内没有环), gcd(0, t) = t。条件变为 s%t==0，这是正确的。
        // 如果 s=0, s%gcd(g,t) 总是 0, 也是正确的，因为可以不行走。
        long long common_divisor = std::gcd(g, t);
        
        if (s % common_divisor == 0) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }

    return 0;
}

复杂度分析的说

时间复杂度: O(N + M + Q * log(T)) 的说。
- Tarjan 算法遍历每个点和每条边一次，是 O(N + M) 的。
- 计算 GCD 的 DFS 也是遍历每个点和每条边一次，所以也是 O(N + M) 的。
- 处理 Q 个查询，每个查询需要计算一次 gcd，其复杂度大约是 O(log(T))，其中 T 是 t 的最大值。
- 所以总时间就是这几部分加起来，非常高效！
空间复杂度: O(N + M) 的说。
- 邻接表需要 O(N + M) 的空间。
- Tarjan 算法和计算 GCD 的 DFS 都需要一些辅助数组，大小都是 O(N) 的。
- 所以总空间由图的存储决定，是 O(N + M)。

知识点与总结

这道题是图论和数论结合的绝佳范例，喵~ 通过它我们可以学到：

强连通分量 (SCC): 环路相关的问题，首先要想到 SCC！所有环都封闭在 SCC 内部，这是一个非常重要的性质。Tarjan 算法是解决 SCC 问题的标准利器。
GCD 的巧妙应用: 看起来毫无规律的一堆路径长度，其实它们的差值都受一个“万能公约数” g 的制约。利用 DFS 和 GCD 找到这个 g 是解题的关键。
丢番图方程: 将问题 (s + k*g) % t == 0 转化为 k*g - m*t = -s 形式的丢番图方程，并利用裴蜀定理 ax + by = c 有解的条件是 gcd(a, b) | c 来求解，是数论中的经典操作。
分解问题的思想: 面对一个复杂问题，先把它拆成几个子问题：图的结构问题（SCC）、路径的代数性质问题（GCD）、最终条件的数论问题（丢番图方程）。一步步解决，整个问题就迎刃而解啦！

希望这篇题解能帮助到你，主人！继续努力，你一定能成为超棒的算法大师的，喵~！

G. Phoenix and Odometers - 题解 ​

比赛与标签 ​

喵喵大意 ~ 题目讲了什么呀？ ​

解题思路大冒险！ ​

第一步：回到起点意味着什么？ ​

第二步：里程表的秘密 ​

第三步：寻找“万能公约数” g ​

第四步：整合起来，解决问题！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​