Gym - 102056C(2018EC final) -Heretical Möbius ——CRT，这神奇的数学公式，你改写对了吗？

本文共计676个文字，预计阅读时间需要3分钟。

题目：判断一个200位的01序列是否在前1e9个沃斯乌斯值中。

给出：分析+意义因为4的倍数一定是0，9的倍数一定是0，等等，16的倍数一定是0。所以，我们可以判断一个200位的01序列是否在前1e9个沃斯乌斯值中。

题意

给出一个长为200的01序列，判断是否在前1e9个莫比乌斯*值中。（这里的莫比乌斯值加了绝对值）

分析

意到因为4的倍数一定是0，9的倍数一定是0……169的倍数一定是0。那么我们可以对4,9,25,49,121,169这6个200以内这质数平方进行考虑。

我们可以枚举起点位置 $x$ 对这6个数的模数，然后用CRT求出 $x$。对每个起点位置，暴力对比即可。不可能存在所有的mu值，只能单个求。

由于0的个数介于65~95，所以符合条件的起点位置并不多，因此不会超时。