题解_牛客博客

只有一个a，考虑模m意义下能构造的c

即 $ax=my+c (x>=1,y>=0)$ 是否有解？
即 $ax+my=c (x>=1,y<=0)$ 是否有解
这个有解性是等价于 $ax+my=c$ 是否有整数解的
如果 $ax+my=c$ 无解，则显然无解。
如果 $ax+my=c$ 有解，不要忘了通解 $x=x_0+m/gcd()t, y=y_0-a/gcd()*t$
因此，可以通过选取一个足够大的 $t$ ，满足 $x>=1,y<=0$
因此，只需要考虑 $ax+my=c$ 是否有正整数解即可

结论

只有一个 $a$ ，考虑模 $m$ 意义下能构造的 $c$ 是 $c=gcd(a,m)\times k$ .

考虑两个a_1,a_2能构造的数

显然是 $a_1x_1+a_2x_2 (x_1,x_2>=0)$ .
显然这个可以表示成 $gcd(a_1,a_2)x (x>=b)$ . $b$ 是一个只与 $a_1,a_2$ 有关的常数
记 $a=gcd(a_1,a_2)$ 。
则变成 $ax=c+my (x>=c,y>=0)$ 是否有解的问题。
用上面考虑一个 $a$ 的时候的道理可以得到等价于 $ax+my=c$ 有整数解。
虽然 $x>=1$ 换成了 $x>=c$ ,但是我们依旧还是可以通过选取一个足够大的 $t$ 调到符合大小限制条件。

结论2

对于两个数 $a_1,a_2$ 在模 $m$ 意义下能构造的数和 $a=gcd(a_1,a_2)$ 在模 $m$ 意义下能构造的数完全一样。

由结论2可以n个数 $a_i$ 合并成一个数 $a$ ，由结论而1可以直接获得答案是 $m/gcd(a,m)$