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 huzujun at 2013-01-21 10:57:55 on Problem 2891
In Reply To:这个题,如果不满足中国剩余定理的话怎么办啊?? Posted by:y07yangruilong at 2007-11-02 22:02:34
> 这个题,如果不满足中国剩余定理的话怎么办啊??就是ki不互素的时候怎么解啊,俺是菜鸟,哪位大牛帮一下啊??
这个题不能直接应用中国剩余定理,因为m的值可能不互素。。。。所以用两两求解的方法来求解(应该是叫迭代吧。。。自己是这么跟别人说的。。。)看下面的例子。。

x = 1 (mod 5)

x = 2 (mod 6)

x = 3 (mod 7)

首先我们把第一个方程写成 x =   5*t+1 ,然后带入第二个方程,得5*t + 1 = 2(mod 6)    ==>  t = 5(mod 6) ;再写成 t = 6*u+5 

则 x = 5*(6*u+5)+1 = 30 *u +26; 再次带入第三个方程,30 *u +26=3(mod 7) 可以得出 u=6(mod 7);

则 u = 7*v+6 ; x = 30*(7*v + 6)+26=210*v+206; 

所以 x = 206(mod 207);

就按照这样不断更新 a*x=b(mod n) 中的a 和 n ,逐次带入来求解。。。。。

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