Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:不清楚算法的可以进来,

Posted by atyuwen at 2008-05-04 19:49:29 on Problem 1061
In Reply To:Re:不清楚算法的可以进来, Posted by:zwood at 2008-02-06 11:57:08
>是啊。 得到的解应该是ax+by=gcd(a,b) 的解。
> 
> 
> 
> LZ的算法有问题啊
> 当gcd(a,b)!=1时
> (ax+by)%gcd(a,b)==0是吧?
> 那么(ax+by)肯定是gcd(a,b)的倍数,也就不等于1
> 所以这种情况下ax+by=1是无解的.
> 
> 所以首先传入的a和b要保证他们互质
> 也就是先做这一步a=a/gcd(a,b);   b=b/gcd(a,b);
> 然后再传递参数.
> 
> 然后最后计算通解的时候
> 应该是
> 对于不定方程ax+by=c的通解为:
> x=x0*c+b*t
> y=y0*c-a*t
> (d=1所以消去了)

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator