这也太强了！
容易想到的是用若干环拼出这个 \(10^{10^{100}}\)，也就是这些环的 \(\gcd \mid 10\)。
之后就不会了。
先正图反图两次 DFS，只留下 \(1\) 所在强连通分量里的边，对正图跑 DFS 生成树，定义其深度从 \(0\) 开始，然后有一个结论是：对于任何正整数 \(a\)，图中存在一个包含 \(1\) 的且长度不是 \(a\) 的倍数的环的充要条件是存在一条图上的边 \((u,v)\) 使 \(dep_{u}+1-dep_v\not\equiv\pmod a\)。
下面是证明。
必要性考虑证明逆否命题，即若不存在一条图上的边 \((u,v)\) 使 \(dep_{u}+1-dep_v\not\equiv\pmod a\)，则图中包含 \(1\) 的环的长度都是 \(a\) 的倍数。这是显然的，由于这样的环深度从 \(0\) 开始，每次移动都相当于深度在模 \(a\) 意义下加 \(1\)，又回到 \(0\)，所以环长一定是 \(a\) 的倍数。
充分性不知道题解在说什么，但是若存在这样 \(dep_{u}+1-dep_v\not\equiv\pmod a\) 的边，就说明 \((u,v)\) 是非树边且 \(u\) 和 \(v\) 是由两条不同的根链便利到的，由于 \(dep_{u}+1-dep_v\not\equiv\pmod a\)，那么 \(1\to u\) 的根链长加 \(1\) 与 \(1\to v\) 的根链长，在模 \(a\) 意义下不同余，也就是两条 \(1\) 到 \(v\) 的路径长不同余。这时候同样是从 \(v\) 回到 \(1\)，两个环长度一定不同余，那么至少有一个不是 \(a\) 的倍数。
这样我们对所有环求 \(\gcd\) 就可以对所有 \(dep_u+1-dep_v\) 求 \(\gcd\)。
点击查看代码
int t;
int n,m;
vector<int> E1[maxn],E2[maxn];
bool vis1[maxn],vis2[maxn];
int dep[maxn];
void dfs1(int u,int d){
vis1[u]=true,dep[u]=d;
for(int v:E1[u]){
if(vis1[v]) continue;
dfs1(v,d+1);
}
}
void dfs2(int u){
vis2[u]=true;
for(int v:E2[u]){
if(vis2[v]) continue;
dfs2(v);
}
}
int main(){
t=read();
while(t--){
n=read(),m=read();
for(int i=1;i<=n;++i){
E1[i].clear(),E2[i].clear();
vis1[i]=false,vis2[i]=false,dep[i]=0;
}
for(int i=1;i<=m;++i){
int u=read(),v=read();
E1[u].push_back(v);
E2[v].push_back(u);
}
dfs1(1,0);
dfs2(1);
int g=0;
for(int u=1;u<=n;++u){
if(!vis1[u]||!vis2[u]) continue;
for(int v:E1[u]){
if(!vis1[v]||!vis2[v]) continue;
if(!g) g=abs(dep[u]+1-dep[v]);
else g=__gcd(g,abs(dep[u]+1-dep[v]));
}
}
if(!g) printf("No\n");
else{
while(g%2==0) g/=2;
while(g%5==0) g/=5;
if(g==1) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
- 题解 AtCoder-ABC AtCoder Return ABC题解atcoder-abc atcoder return 题解atcoder-abc atcoder abc atcoder-abc atcoder-abc atcoder 128 abc atcoder-abc medicine atcoder abc g-rearranging atcoder-abc rearranging atcoder atcoder-abc蛋糕atcoder 15095 atcoder-abc continuous atcoder index 题解atcoder-at_abc atcoder abc 题解atcoder abc 295