cf103202I. Rise of Shadows

题目描述

题解

很不会同余方程呜呜呜。

可以看成追击问题,于是我们经过化一些式子后能够得到个不等式:

如果对于一个整数 $k in [0,HM)$ ,存在整数 $x$ ,满足

$$xHM-A le k(H-1) le xHM+A$$

那么这个 $k$ 就满足要求

因此,有 $-A le k(H-1)-xHM le A$

若我们规定,对 $HM$ 取模的值的范围为 $[-HM/2,HM/2]$ ,故就要满足

$$-A le k(H-1) mod HM le A$$

因此,设 $g=gcd(H-1,HM)$ ,根据剩余系,对于 $k in [0,HM/g)$ ,有 $k(H-1) mod HM= ...-2g,-g,0,g,2g,...$ ,而且是一一对应的。

因此,存在 $A/g imes 2+1$ 个 $k$ ,满足 $k(H-1) mod HM$ 在 $[-A,A]$ 之间。

而有 $g$ 轮这样的 $k$ 的取值,故答案为 $g imes (A/g imes 2+1)$ 。

然后就是需要特判 $A=HM/2$ 的情况就好了。

原文地址:https://www.cnblogs.com/xjqxjq/p/15506638.html