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

谁帮忙啊 ?

Posted by lysaitl at 2009-09-28 13:14:11 on Problem 3243
  我照这个思路写的怎么就差的很远了 ?
    是这个思路写的不好吗 ?
显然如果模的数是素数,那问题就很简单
因为对于素数P
有
a^(-m) mod P=a^(P-m-1) mod P
那么这题P不是素数,于是也可以套用baby-step giant-step的思想
既PKU 3243 Clever Y
那么如何套用?
比如解K^x mod P= N
那么按照上面的算法
令G=gcd(K,N,P)
然后
K'=K/G;
N'=N/G;
P'=P/G;
   1. m ← Ceiling(√P')
   2. For all j where 0 ≤ j <= m:
         1. 把(j,(K^j)%P') 入Hash表
   3. 计算K^m
   4. Y← K'.
   5. For i = 0 to m:
         1. 解模方程: Y*X=N'(mod P') 得到所有的可能的解(0..P'-1内),令ans=inf
             a.如果有解:对于每一个解:
                  1. 检查解是否在Hash表中
                  2. 如果是 ans=min( im + j,ans).
                  3. 如果ans!=inf,return ans+1,否则Y ← Y*(K^m),Y%=P'.
             b.无解:


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