[ABC306G] Return to 1
题意
给一张有向图，问有没有方案在从 \(1\) 号点出发，在图上刚好走 \(10^{10^{100}}\) 步之后重新回到 \(1\) 号，无重边，无自环。
题解
显然这个题目肯定和环有关，我们设第 \(i\) 个经过 \(1\) 的环的长度为 \(x_i\) ，经过的次数为 \(a_i\) ，显然我们要求的是一下方程有无解。
\[\sum a_ix_i = 10^{10^{100}} \]根据裴蜀定理这个方程有解当且仅当
\[gcd(x_1,x_2,x_3...)|10^{10^{100}} \]但是有解不一定有用，还要有非负整数解才行，下面有一个结论是我以前不知道的。
\[ax+by=c(a,b,c\in \mathbb{Z},gcd(a,b)=1) \]这个方程有正整数的充分不必要条件是 \(c>ab\) 证明不会证，可以拓展到多个。
这道题的 \(c\) 足够大，所以可以保证解是正整数，所以我们要保证 \(gcd(x_1,x_2,x_3...)\) 的因数只有 \(2,5\) 。
但这样还没完，我们会发现有些不包含 \(1\) 的环也是可以走很多次的，这也能对答案做贡献。
我们将不包含 \(1\) 的环称为小环，包含 \(1\) 的环称为大环，由于小环不包含 \(1\) 显然只能依附于大环之上。
而我们走过一次小环所在的大环之后，这个小环就可以随意走了。
而这个方程又一定会有正整数解，所以每一个大环都至少会走一次，所以小环也是可以随便走的，小环就和大环等价了。
到最后我们只需要将图中所有一定不会走到的点删掉，然后对所有的环长求一个 \(gcd\) 即可。 code
...
感觉裴蜀定理与这样的方程是好想的，小环与大环的关系其实也是水到渠成的，有正整数解这个结论可以记一记。
标签：小环,10,方程,Return,gcd,ABC306G,大环,正整数 From： https://www.cnblogs.com/snow-panther/p/17513071.html