这一道题目最好记住,就是两个模数之间在互相作用
首先转化一下,我们枚举其中一个集合然后快速查询另一个集合
也就变成了\((a_i+kP)mod\: Q∈B\)
然后看这篇文章的建模
解释一下
它是将\([0,Q)\)中的每一个数弄成一个环,就像下面这样
然后加一个\(P\)就相当于瞬时间走\(P\)步
假设走了\(k\)个\(P\),也就有\(i+kP\equiv i (mod\: Q)\),即\(kP\equiv 0 (mod\: Q)\)
这个式子的意思就是这个\(kP\)要最小,而且\(kP\)既是\(P\)的倍数也是\(Q\)的倍数,那当然就有\(kP=lcm(P,Q)\)
然后脑子模拟一下这个过程,就会发现这个环是独立的(也就是剩下的论述显然成立)
然后就是细节了