题解：CF1515G Phoenix and Odometers
900102bj
·
·
题解
CF1515G Phoenix and Odometers
首先进行缩点，对于一个点，与它不在同一连通分量的点无法形成回路，所以对每个连通分量分别计算。
假设一个点 u，有两个长度为 a 和 b 的环，那么就相当于找两个非负整数 x 和 y，使得 ax+by=w，其中 w 为题中的路径长，根据裴蜀定理得到上述方程成立当且仅当 \gcd(a,b)\mid w。
考虑如何求出 \gcd(a,b)，即点 u 所有环长的 gcd。
首先在强连通分量中存在四种边：树边、横叉边、返祖边、前向边。
举个例子：
假设根节点为 1，根节点通过树边到节点 u 的路径长度为 dis_{u}。
以横叉边 5\to 3 这条边为例，设它的边权为 w。因为这些点在同一连通分量且它是横叉边，说明 3 这边已经可以形成回到 1 的一条回路了。
所以其中一条回路为 1 通过树边连向 3，3 再通过一些非树边连回 1，大体路径为 1\to 3\to 1，长度可以表示为 dis_{3}+val(3,1)。
又因为当前的横叉边 5\to 3，产生了一条新的回路。
这两条回路的 gcd，可以使用辗转相减进行化简，将公共路径部分减掉，则 gcd 为 $\gcd(dis_{3}+val(3,1),dis_{5}+w-dis_{3})$。
这样对于一条横叉边 $u\to v$，对 gcd 产生的贡献为 $dis_{u}+w-dis_{v}$。
然后通过分析发现，返祖边和前向边对 gcd 的贡献也是 $dis_{u}+w-dis_{v}$，即所有的非树边，对答案的贡献是相同的。
求出所有环长的 gcd，设为 $g$，然后根据题意得出 $a\times g+s=b\times t$，再一次使用裴蜀定理得到 $\gcd(g,t)\mid s$。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,q;
const int maxn=2e5+10;
struct node{
int to,nxt,w;
};
node e[maxn];
int head[maxn],tot;
void add(int u,int v,int w){
++tot;
e[tot].to=v;
e[tot].nxt=head[u];
e[tot].w=w;
head[u]=tot;
}
int dfn[maxn],low[maxn],st[maxn];
bool vis[maxn];
int scc[maxn];
int res,tp,cnt;
void tarjan(int u){
dfn[u]=low[u]=++res;
st[++tp]=u;
vis[u]=1;
for(int i=head[u];i!=0;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
++cnt;
while(st[tp]!=u){
scc[st[tp]]=cnt;
vis[st[tp]]=0;
--tp;
}
scc[st[tp]]=cnt;
vis[st[tp]]=0;
--tp;
}
}
int dis[maxn],g[maxn];
bool tag[maxn];
void dfs(int u,int cur){
tag[u]=1;
for(int i=head[u];i!=0;i=e[i].nxt){
int v=e[i].to;
int w=e[i].w;
if(scc[v]!=cur){
continue;
}
if(tag[v]){
g[cur]=__gcd(g[cur],dis[u]-dis[v]+w);
continue;
}
dis[v]=dis[u]+w;
dfs(v,cur);
}
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i);
}
}
for(int i=1;i<=n;i++){
if(!tag[i]){
dfs(i,scc[i]);
}
}
scanf("%lld",&q);
while(q--){
int u,s,t;
scanf("%lld%lld%lld",&u,&s,&t);
if(s%__gcd(g[scc[u]],t)==0){
printf("YES\n");
}
else{
printf("NO\n");
}
}
return 0;
}
```