随笔 - 1, 文章 - 0, 评论 - 0, 引用 - 0
数据加载中……

2011年8月8日

POJ1061

对于给定的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

posted @ 2011-08-08 23:43 王子野心 阅读(389) | 评论 (0) | 编辑 收藏