Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:不清楚算法的可以进来,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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator