主要思路
复盘一年前做过的题,现在感觉确实简单。
考虑表示成 \(d’ \in A, d = d’ + xP\),然后算有多少个 \(x\) 满足 \(d\) 在 \(B\) 中。暴力直接枚举。考虑优化暴力,我们发现这个肯定是有个循环节的,长度为 \(\text{lcm}(P, Q)\),这个可以做一个轻微的优化。
我们考虑把这个模 \(Q\) 想成一个环形带,然后把起始位置为 \(start_pos\) 的 \(d \in B\) 在这个纸带上进行标记、做前缀和,为了方便判断前缀和的加减顺序,我们还要标记排名。
计算的时候,对于 \(A_i\),我们需要知道这个元素 \(T\) 经历了多少次(\(cnt\))循环,然后完整循环的总和算进去。算完这个之后,我们来算开头和结尾。开头位置肯定就是 \(A_i \bmod Q\),结尾则是 \((A_i + cnt * P \bmod loop) \bmod Q\)。然后前缀和搞下即可。
Continue reading →