题解

计数器

http://www.nowcoder.com/questionTerminal/860cd43115b34020b4b8bd1a9cd4091f

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

是否有解?
是否有解
这个有解性是等价于是否有整数解的
如果无解,则显然无解。
如果有解,不要忘了通解
因此,可以通过选取一个足够大的,满足
因此,只需要考虑是否有正整数解即可

结论

只有一个,考虑模意义下能构造的.

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

显然是.
显然这个可以表示成.是一个只与有关的常数

则变成 是否有解的问题。
用上面考虑一个的时候的道理可以得到等价于有整数解。
虽然换成了,但是我们依旧还是可以通过选取一个足够大的调到符合大小限制条件。

结论2

对于两个数在模意义下能构造的数和在模意义下能构造的数完全一样。


由结论2可以n个数合并成一个数,由结论而1可以直接获得答案是

全部评论

相关推荐

2 收藏 评论
分享
牛客网
牛客企业服务