CF1515G - Phoenix and Odometers

题目大意

给定一张带权有向图，每次查询$v,s,t$表示从$v$出发并且回到$v$，可以经过重边

判断是否存在经过路径总长$l$满足$l+s\equiv 0 \pmod t$

分析

显然$v$只能在其自己的强连通分量里走，并且分量内部的任意一个环都是可达的

由于是模意义下，所以环的贡献可以抵消，环之间可以无限叠加

根据裴蜀定理，能够生成的数就是是$\gcd(len_i)$的倍数

只需预处理强连通分量内部的环，判断$\gcd(len_i,t)|\gcd(s,t)$即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

const int N=2e5+10;

int n,m;
struct Edge{
	int to,nxt,w;
}e[N];
int head[N],ecnt;
void AddEdge(int u,int v,int w){
	e[++ecnt]=(Edge){v,head[u],w};
	head[u]=ecnt;
}

ll G[N],S[N];
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }
int t[N],low[N],dfn,stk[N],ins[N],top,id[N],scc;
ll dis[N];

void dfs(int u){
	ins[stk[++top]=u]=1,low[u]=t[u]=++dfn;
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(!t[v]) {
			dis[v]=dis[u]+e[i].w;
			dfs(v),cmin(low[u],low[v]);
		} else if(ins[v]) {	
            // 不管是横边还是返祖边，长度都是dis[u]-dis[v]!!!
			cmin(low[u],t[v]);
			G[u]=gcd(G[u],dis[u]-dis[v]+e[i].w);
		}
	}
	if(low[u]==t[u]) {
		++scc;
		for(int v=-1;v!=u;) {
			ins[v=stk[top--]]=0;
			id[v]=scc,S[scc]=gcd(S[scc],G[v]);
		}
	}
}

int main(){
	n=rd(),m=rd();
	rep(i,1,m) {
		int u=rd(),v=rd(),w=rd();
		AddEdge(u,v,w);
	}
	rep(i,1,n) if(!t[i]) dfs(i);
	rep(_,1,rd()) {
		int u=rd(),s=rd(),t=rd();
		s=gcd(s,t),t=gcd(t,S[id[u]]);
		puts(s%t==0?"YES":"NO");
	}
}