C题暴力枚举a的系数然后exgcd,复杂度是对的吗

我看很多人都是把a的系数暴力枚举到1e6,然后解不定方程
会不会在枚举的范围内无解呢?
会不会存在x在1e9,1e10,1e11这种规模的情况呢
全部评论
考虑a个b和b个a是等价的,所以可以使x小于min(b,c)
2 回复 分享
发布于 2020-03-28 00:20
只要让k-ax能被gcd(b,c)整除即可  而b、c只有1e5  也就是gcd(b,c)最大只有1e5 意味着每1e5个必有一个可以进行exgcd
点赞 回复 分享
发布于 2020-03-27 23:44

相关推荐

伟大的烤冷面被普调:暨大✌🏻就是强
点赞 评论 收藏
分享
10-24 11:10
山西大学 Java
若梦难了:哥们,面试挂是很正常的。我大中厂终面挂,加起来快10次了,继续努力吧。
点赞 评论 收藏
分享
评论
点赞
1
分享
牛客网
牛客企业服务