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\)，产生了一条新的回路。
\(1\) 通过树边连向 \(5\)，\(5\) 通过横叉边连向 \(3\)，\(3\) 通过一些非树边连回 \(1\)，大体路径为 \(1\to 5\to 3\to 1\)，长度为 \(dis_{5}+w+val(3,1)\)。
这两条回路的 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\)。
#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;
}
