自动搬运

查看原文

来自洛谷，原作者为

	xuanxuan001 生活就像愤怒的小鸟，失败后总有几只猪在笑。

搬运于2025-08-24 23:15:49，当前版本为作者最后更新于2025-05-22 19:22:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看了很久才明白，写篇题解记录一下，竟然还是遥遥领先的最优解？

挂个 qoj 链接和一个关联题目（其实这个题里面的思想到最后才用到，我就是先看了这题导致被误导了）。

首先缩点，对于一个强连通分量（下称 SCC），可以发现它其实到最后的周期就是所有环长的 $\gcd$，因为这些环大概可以任意组合，由裴蜀定理可以发现就是，具体求可以以某个点为关键点出发求 dfs 树，然后对非树边按两边深度求个环长就行了，虽然这样的环里面有些边时反向的，但无所谓，因为它是强连通，总能绕回去的，设这个 $\gcd$ 为这个 SCC 的权值，如果这个 SCC 里没有回路，也即只有一个点，那么认为它没有权值。跨 SCC 的边按照两边在自己的分量里的距离可以算出一个新的在 SCC 之间的“长度”。

然后对于一个从 $1$ 所在分量到 $n$ 所在分量的路径，如果它不经过有权值的 SCC，那么这条路径显然对答案不产生贡献，否则同样由裴蜀定理，它的周期是经过的所有 SCC 的权值的 $\gcd$，而它的相位（也即 $x \equiv a \bmod r$ 中的 $a$）可以通过经过的跨 SCC 的路径的长度和求得。

由于题目中保证了环长不超过 $100$，因此有 $a < b \le 100$，所以可能的 $(a,b)$ 数量可以接受，那么所有路径的 $(a,b)$ 可以在 DAG 上容易求得，注意在遇到第一个有权值的 SCC 之前的状态需要特殊考虑，可以先将所有的模数的情况都求一遍并给每个 SCC 对应模数的情况作为初始值。

那么现在求出了所有的 $(a,b)$，将相同的 $a$ 的数对合并成为一个周期为 $a$ 的串，需要求的其实就是所有的这些周期串的并的最小周期。发现取并不是很优美，可以取反后改为取交，这样就等于是一个 CRT 合并求解的过程，只是每个同余方程不要求余数等于特定值而要求属于一个集合，但本质是差不多的。下面的讨论一律按照取交写，称最后取交后的串为最终串，不难发现最终串其实就是这个 CRT 的解集。

首先先给每个串求出最简周期，这样处理后所有的周期串都不存在周期。首先考虑所有的 $a$ 两两互质的情况，发现此时答案就是 $T = \operatorname{lcm} a$，首先不难发现 $T$ 一定是答案的倍数，然后考虑如果存在一个长度是 $T$ 的因数且不是 $T$ 的周期，那么一定存在一个 $a$ 不是这个周期的因数，那么由于这个周期串没有周期，所以这个小于 $T$ 的周期一定会因此不成立。

那么为什么不能拓展到不互质的情况呢？考虑很简单的一个例子，有两个周期串，一个01，一个0111，不难发现周期是 $2$，因为第二个周期的第三个位置那个 $1$ 根本用不到，所以现在考虑去除这些串中这样的位置，然后用同样的做法就可以了，因为此时一个串中的不同一定会导致最终出来的串某个位置不同。

那么分析一下这样的位置是什么样子，相当于把它所在的这个串改成只有这个位置是 $1$ 后输出的结果串为全 $0$，也即这个同余方程无解。这时转而取考虑找到所有不需要被去除的位置，也即按上述方式更改后有解，这时转变统计思路，考虑枚举最终串的每个位置，可以代入每个方程验证出这个位置是否为 $1$，如果是 $1$ 的话所有周期串的对应位置就都可以标记为合法，虽然依次这些位置很不现实，但它具有拓展意义。

考虑刚才所有周期长度互质的情况为什么不需要考虑这些问题，因为在它们互质的时候不管同余方程是啥用 CRT 一定能合并出来一个解。

那么现在考虑一般情况怎么变成一个全部互质的情况，考虑如果先枚举一个数 $x$ 并只考虑最终串中所有模一个常量 $C$ 余 $x$ 的位置，那么此时一个长度为 $a$ 的周期就变成了一个长度为 $\dfrac a{\gcd(a,B)}$ 的周期。那么如果这时的所有周期两两互质并且没有一个全 $0$ 的周期序列让解集为空集，那么我们就可以将每个周期对应的 $1$ 的位置标位合法了，因为它们都可以在这个同余的集合中找到一个解。

那么这个 $C$ 需要取多少呢？这时就用到了最前面挂的那道链接题目了，发现只需要取到 $2520$ 即可，此时任何一个不超过 $100$ 的数不会有两个质因子的次数同时超过它，否则乘起来就爆 $100$ 了。此时直接按照原题中子任务 6 的做法做就可以了，注意此时会产生许多周期为 $p^k$ 的周期，需要将它们合并以保证所有周期长度两两互质，然后就做完了。

代码就不贴了，直接上 qoj 看就行。