2019-09-13 15:18 已编辑南京航空航天大学 Java

关注

题解

计数器

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

只有一个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)$

全部评论

推荐最新楼层

10-30 21:23

美团_HR(准入职员工)

浩鲸科技内推，浩鲸科技内推码

浩鲸科技测试工程师（福州）timeline2.25投递3.13一面3.18二面一面✅线上进行，面试官很友好，深挖简历和项目，问得很细，细到比赛里使用的软件，还问了测试工程师需要具备什么特质；专业知识问了mysql相关的两个问题，只删除数据不删除整个表用什么语句命令？有个表格，想要按照什么要求进行升序排列，用什么语句？自我感觉mysql回答的不好，毕竟没怎么看过但是没想到还是收到了二面邀请全程持续二十分钟左右🕧二面✅线上进行，面试官更友好大多时候是在闲聊，简历问的很少，还让我用英文介绍自己的家乡（我也是二面才发现我投的是国际的岗位）全程持续30分钟左右🕧在讨论到我喜欢出差时，面试官觉得我更适...

点赞评论收藏

10-29 16:30

广东工业大学材料工程师

月薪1W在老家直接躺赢

身边同学留本地的大多 6-8k，我这个 1W 到手快 9k，房租 1500 能租一室一厅，吃饭通勤一个月 2000 足够，每个月还能攒下 5k+😆 不用挤地铁、不用抢工位，下班就能回家吃妈妈做的饭，感觉这个薪资在二三线城市已经是中上水平，性价比直接拉满，秋招能拿到真的知足了！

牛泪中：每天都能见老妈就是最大的幸福

校招生月薪1W算什么水平

点赞评论收藏

09-22 21:26

阿里云_阿里云智能_安全工程师(准入职员工)

秋招结束

腾讯意向 字节意向京东意向蚂蚁意向网易意向百度意向……………上面都是假的但阿里云意向是真的

清辉夜凝l：点赞关注收藏都是假的举报是真的

点赞评论收藏

10-20 15:26

门头沟学院 Java

我这情况正常吗

27届211本，投了127份简历，只有4个面试

桥头牛油火锅：这个比例不正常，简历的话项目经历放中间，项目功能分点可以再明确点，前面加“·”或者“1 2 3”，另外简历上的照片可以去外面摄影店拍一下，以后也会用到的，hr筛人也是多少会看的，毕竟世界是一个巨大的卡颜局嘛，还有有些hr由于消息太多可能没看到，后面可能会回来找你，要简历的还会多一点，我也是普2本，比例大致是600:90:15:3，当然我实力不太够，拿的offer比较少，慢慢来吧

点赞评论收藏