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 |
谁帮忙啊 ?我照这个思路写的怎么就差的很远了 ? 是这个思路写的不好吗 ? 显然如果模的数是素数,那问题就很简单 因为对于素数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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator