ABC306G Return to 1 题解

六楼溜刘 · 2023-06-19 14:28:31 · 题解

题意

给你一张有 N 个结点 M 条边的有向图，问能不能经过恰好 10^{10^{100}} 条边从结点 1 出发回到结点 1，可以重复经过同一个点或边。

题解

首先看到 10^{10^{100}} 这个大数就容易想到这道题肯定和数论有关，很容易得出初步思路：计算出所有由 1 出发能到达 1 的路径长度，用某种方法凑出 10^{10^{100}}。

但这个思路本身有点小问题，比如这种情况：

容易想到只需要重复走 1 \to 2 \to 3 \to 2 \to 3 \to 1 这条路径即可，由于 10^{10^{100}} 是 5 的倍数所以显然可以，但从 1 出发到达 1 的路径要么就统计不到 2 \to 3 \to 2 这个环（只统计简单路径），要么就会死循环。

关于如何解决这个问题，这个我们放到最后讲。

刚刚提过这个问题和数论有关，不妨把它放到一个代数的情景下，就转化成了这个问题：

求证 a_1x_1+a_2x_2+\dots+a_Kx_K=10^{10^{100}} 是否有正整数解。

多元一次不定方程有解性证明让我们联想到什么？裴蜀定理！

简单讲一下裴蜀定理：

不定方程 ax+by=c(a,b,c\in \mathbb{Z}) 有整数解当且仅当 \gcd(a,b)\mid c。

这里讲一个我比较喜欢的证明（主要是其他的我看不懂）。

设集合 A=\{ax+by\;|x,y\in \mathbb{Z}\}，也就是有整数解时所有 c 可能的取值。

假设集合 A 中的最小正整数为 s，易证 A 中所有数都被 s 整除，假如存在 n \in A 且 s \nmid n，那么可以令 n=ps+q(0 <q<s)，显然 q 可以由 n 和 s 线性变化得到，所以它在集合 A 中，与 s 是最小矛盾。

接下来证明 s=\gcd(a,b)，转化为证明 s\mid \gcd(a,b) 且 \gcd(a,b) \mid s，

首先，设 s=ax_0+by_0，显然 \gcd(a,b)\mid ax_0 且 \gcd(a,b)\mid by_0，故 \gcd(a,b) \mid s。

然后，当取到 x=1,y=0 时， ax+by=a，故 a\in A，同理，b\in A，又由于 A 中所有数都被 s 整除，所以 s \mid a,s \mid b，故 s \mid \gcd(a,b)。

综上，s=\gcd(a,b)

然后这个证明还可以拓展到多个数（比如 ax+by+cz=d），~~我邀请读者把这当做一种练习~~。

拓展到多个数得到的结论就是这道题要用的了，注意到 10^{10^{100}} 所含的质因子仅有 2 和 5，由于这个数足够大我们几乎可以把它看做 2^{\infty}\times5^{\infty}，所以只要找到多个合法的环（指上文所说 1 \to \cdots \to 1 的和路径上额外的环）使得它们长度的 \gcd 包含的质因子仅有 2 和 5（注意 \gcd=1 也是可行的）。容易发现一个数集中所有数的 \gcd 一定是其中部分数 \gcd 的约数，不妨直接求出所有路径长度的 \gcd 来判断是否有解。

注意到裴蜀定理只能保证有整数解，我们还需要证明它有正整数解。

首先有个比较经典的结论：

对于不定方程 ax+by=c（a,b,c\in \mathbb{Z},\gcd(a,b)=1），它有正整数解的充分不必要条件是 c> ab。

这一部分类似于 P3951 [NOIP2017 提高组] 小凯的疑惑，我还是简单证明一下。

设不定方程 ax+by=c(\gcd(a,b)=1) 有一组整数特解 x=x_0,y=y_0，那么它的通解是什么呢？设另一组解为 x_1,y_1，令 x_1=x_0+\lambda，故 ax_0+a\lambda+by_1=c，则 ax_0+b(y_1+\frac{a}{b}\lambda)=c，即 y_1=y_0-\frac{a}{b}\lambda，由于 x_1,y_1 是整数，不妨设一整数 \theta=\frac{1}{b}\lambda，可得方程通解为：

\begin{cases}x&=x_0+b\theta\\y&=y_0-a\theta\end{cases}

其中 \theta 为任意整数。

回到原来的证明，设 c=ab+z(z\in \mathbb{Z},z>0)，原方程可化为：ax+by=ab+z。

假如 x_0,y_0 是上方程的一组特解，易得：

\begin{cases}x&=x_0+b\theta\\y&=y_0-a\theta\end{cases}

另外我们可以得到 y 关于 x 的函数关系式：y=\frac{ab+z-ax}{b}，这关于 x 的增加而线性减小。

由通解的那个式子容易发现我们可以把 x 控制在 [1,b] 这个范围内，那么最坏情况就是 x=b，此时 y=\frac{z}{b}，由于 b>0,z>0 ，所以 y>0，结合裴蜀定理可证 y 为正整数。

此处我们用 a_1,a_2,\dots a_K 来表示所有环的长度组成的数列。

首先可以列出方程 a_1x_1+a_2x_2=y_1（假如 \gcd(a_1,a_2)\ne 1 我们可以左右同时除以 \gcd 所以不影响，可以认为 \gcd(a_1,a_2)=1），为保证有整数解， y_1>a_1a_2，此时不妨用 y_1 来替代 a_1 和 a_2，原数列变为 y_1,a_3,a_4\dots a_K。

接下来同理，得到 y_2>y_1a_3>a_1a_2a_3，最终得到 y_{K-1}>a_1a_2a_3\dots a_K，也就是说只要原方程等号右侧的数足够大就必定有正整数解。

那么 10^{10^{100}} 算不算一个足够大的数呢？由于最多有 M 条路径（假设存在有自环且全是自环），每条路径长度最大为 M（假设只有一条路径），在这种完全不可能的情况下，y_K=M^M，那么 M 最大是多少呢？答案是 2 \times 10^5，此时 y_K=2^{2\times 10^5}\times10^{2\times 5\times 10^5}，远小于 10^{2\times 10^6}，更是比 10^{10^{100}} 小，肯定有正整数解。

~~其实也可以感性理解一下，这个数太大了，也就是说只要能凑出某个只含有质因子 2 和 5 的数就能凑出它。~~

现在难点都证明完了，我们考虑如何统计所有环的长度。

首先，我们不能直接用 dfs 统计，前面已经说过了。

考虑用 dfs 随便建一棵外向树 T_1 包含尽量多的结点，再随便建一棵内向树 T_2 包含尽量多的结点，那么一个环在这两棵树上应该长啥样呢？下文为方便叙述，设点 i 在 T_1 中与 1 的距离为 dis_i。

~~最近 csacademy.com 炸了将就一下。~~

在上图中，黑色和绿色的箭头表示有向边，蓝色是生成的外向树 T_1，红色是内向树 T_2，涂黑的结点是点 1。

我们发现，假设存在一条边 u \to v，这条边不在 T_1 中，且 v 在 T_2 中（比如点 A 就不在 T_2 中），点 u 在 T_1 中（比如点 B 就不在 T_1 中），其实上图中四条绿边就是，那么就存在一个长度为 \lvert dis_u+1-dis_v \rvert 的环。

这时候细心的读者就会发现问题了，比如左边那条边算出来就是 1，而并不存在一条长度为 1 的环，这不会影响答案吗？其实它和那条长度为 4 的环拼起来就能得到一条新的路径，好巧不巧这条新路径的长度刚好就是 1+4=5，而 \gcd(n,n+k)=\gcd(n,k)（辗转相除法，自己分类讨论证一下），之前说过我们只要求出所有路径长度的 \gcd 再判断其质因子是否只含有 2 和 5 即可，所以这对答案并无影响。

而下面的那条边，它算出来是 2，这是一个在某条路径“中间”的小环，之前证过了必然存在正整数解，也就是说它附属的那条路径必然经过至少一次，我们利用这经过的一次把该跑的全跑完即可（感性理解一下），这就解决了开头提出的那个问题。

综上，整理一下整个实现过程：

分别建正反两无向图。
在正图上做 dfs 算出每个点和结点 1 在外向树的距离，在反图上做 dfs 判断某个点是否在内向树上。
枚举 u，找到所有合法的 v，直接统计所有路径长度的 \gcd。
判断 \gcd 是否含有 2 和 5 以外的质因子，得到答案。

code

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);++i)
#define fordown(i,s,e) for(int i=(s);i>=(e);--i)
using namespace std;
#define gc getchar()
int read(){//快读
    int x=0,f=1;char c;
    while(!isdigit(c=gc))if(c=='-')f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
const int N=2e5+5,inf=0x3f3f3f3f;
int t,n,m;
vector<int> e[N],re[N],nt[N];//正图，反图，不在外向树上的边
int ret[N],dpt[N];//能否回到 1，从 1 到该节点的距离
int vis[N];
void dfs(int x){//建外向树
    vis[x]=1;
    for(auto i:e[x]){
        if(vis[i]){
            nt[x].push_back(i);
            continue;
        }
        dpt[i]=dpt[x]+1;
        dfs(i);
    }
}
void dfs1(int x){//建内向树
    vis[x]=1;
    for(auto i:re[x]){
        if(vis[i]){
            if(i==1) ret[1]=1;//特判结点 1
            continue;
        }
        ret[i]=1;
        dfs1(i);
    }
}
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
signed main(){
    t=read();
    while(t--){
        n=read();m=read();
        forup(i,1,n){//注意清空
            e[i].clear();
            re[i].clear();
            nt[i].clear();
        }
        forup(i,1,m){
            int u=read(),v=read();
            e[u].push_back(v);
            re[v].push_back(u);
        }
        forup(i,1,n){
            ret[i]=vis[i]=0;
            dpt[i]=-1;
        }
        dpt[1]=0;
        dfs(1);
        forup(i,1,n){
            vis[i]=0;
        }
        dfs1(1);
        if(!ret[1]){//如果 ret[1]=0 说明整个图不存在包含结点 1 的环，无解。
            puts("No");
            continue;
        }
        int G=-1;
        forup(i,1,n){
            for(auto v:nt[i]){
                if(!ret[v]||dpt[i]==-1) continue;
                if(G==-1){//直接统计 gcd
                    G=abs(dpt[i]+1-dpt[v]);
                }else{
                    G=gcd(G,abs(dpt[i]+1-dpt[v]));
                }
            }
            if(G==1) break;//如果等于 1 就不可能再变小了，直接 break
            //其实这里还可以加一些其它剪枝，但是我懒得搞
        }
        while(!(G%2)) G/=2;
        while(!(G%5)) G/=5;//去掉所有质因子 2 和 5，判剩下的
        puts(G==1?"Yes":"No");
    }
}