C++博客-半壁江山の圣灵玉

C++博客-半壁江山の圣灵玉http://www.cppblog.com/Holy-Jade/半壁江山zh-cnTue, 09 Jun 2026 17:41:05 GMTTue, 09 Jun 2026 17:41:05 GMT60POJ1061http://www.cppblog.com/Holy-Jade/archive/2011/08/08/152825.html王子野心王子野心Mon, 08 Aug 2011 15:43:00 GMThttp://www.cppblog.com/Holy-Jade/archive/2011/08/08/152825.htmlhttp://www.cppblog.com/Holy-Jade/comments/152825.htmlhttp://www.cppblog.com/Holy-Jade/archive/2011/08/08/152825.html#Feedback0http://www.cppblog.com/Holy-Jade/comments/commentRss/152825.htmlhttp://www.cppblog.com/Holy-Jade/services/trackbacks/152825.html

对于给定的x,y,m,n,L;

当m=n的时候必定无解。

可以假设m>n;

那么对于答案a

有(am-x)-(an-y)=kL

可以化成a(m-n)+y=kL+x

也可化成a(m-n)-kL=y-x

显然，如果(y-x)%gcd(m-n,L)!=0,无解

令Q=a(m-n)+y=kL+x

则Q%(m-n)=y

Q%L=x

我们可以枚举a，求出Q，判断是否有Q%L=x

这种方法会TLE

更好的方法是枚举k，判断Q%(m-n)=y

需要注意的是，m-n有可能小于y

王子野心 2011-08-08 23:43 发表评论

]]>