2026 年山东预赛

思路

莫比乌斯记号可直接理解为容斥系数：由不同质因数组成的乘积，取奇数个质因数时记负一、偶数个时记正一；含平方质因子的因数记零。小数部分是实数减其向下取整，属于 $[0,1)$。

想法从哪来：与固定整数互素的模式按这个整数周期重复，所以先剥去完整周期，误差只来自最后一段。短区间里，互素等价于避开每个质因数的倍数，最直接的计数工具是容斥；主项正好把每个倍数计数中的取整去掉，留下有限个小数部分误差。 逐项用小于一估计可能太松。注意容斥系数总和为零，因此可以从所有小数部分同时减去二分之一，而不改变总误差。这样每项绝对值只需按二分之一计，误差界立刻减半。最后只依赖不同质因数个数，再用这些质因数的最小可能乘积和原整数的平方根比较，保证严格小于所需界。

与 $m$ 互素具有模 $m$ 的周期性，先把 $n$ 化到一个不完整周期 $0\le r<m$。 对这个短区间用容斥原理写成莫比乌斯求和；把每个取整误差以 $1/2$ 为中心，可把粗略的 $2^{\omega (m)}$ 误差改进为 $2^{\omega (m)-1}$，再与 $\sqrt{m}$ 比较。