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

这样的话n1和n2不一定互质，不好用中国剩余定理求同余式组，难道暴力？？？？

Posted by 123qq456 at 2009-05-19 21:14:10
In Reply To:见内。 Posted by:harry at 2008-11-18 20:05:01 
> 已知 r*r = x (mod n) 求所有的 r' 使得模方程成立
> r' * r' - r * r = k * n;
> 即 (r' + r) * (r' - r) = k * n;
> 枚举n的因子, 将n拆成n1, n2, 使得 n = n1 * n2
> 则只需解模方程组 r' + r = 0 (mod n1) r' - r = 0 (mod n2)
> 计算出所有 小于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