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;
}