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

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 on 2011-08-08 23:43 王子野心 阅读(389) 评论(0)  编辑 收藏 引用 所属分类: 龙神手札（一）


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理