| ||||||||||
| 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