首页 > 代码库 > bzoj2480 Spoj3105 Mod
bzoj2480 Spoj3105 Mod
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2480
【题解】
大步小步算法(BSGS)
一直觉得BSGS不大优美因为算法里混杂着一个求逆元,这对推exgcd要好久的人不大兹磁啊。。
参考:http://blog.miskcoo.com/2015/05/discrete-logarithm-problem
顺带介绍一下BSGS算法。
普通的BSGS:(p为质数)
设m = ceil(sqrt(P))
那么设A^(am+b)=B (mod P)
那么有(A^m)^a = B * A^(-b) (mod P)
那么把枚举右边所有取值(m种),用map存下,然后枚举a取值(m种),map查表即可。
复杂度O(根号m*(logm))(看STL_map还是手写hash)
扩展的BSGS:(A,P)>1
我们转化模方程:A^x+kP=B(k为整数)
那么令g=(A,P),有:A/g*A^(x-1)+kP/g=B/g
如果B不能被g整除那么肯定无解。
然后我们得到了新的方程A^(x-1) = B/g * (A/g)^(-1) (mod P/g)
(注意右边不能约掉)
然后我们按照这个步骤一直下去直到(a,p)=1,用普通BSGS解即可。注意加上化成BSGS需要的次数cnt。
好了我们发现要一坨逆元,怎么办?
考虑普通BSGS里的逆元:
因为p不是质数了所以这个逆元很鬼畜啊要用exgcd求。
不用急,我们让x=am-b即可。这样式子就变成了:
那么有(A^m)^a = B * A^b (mod P)
不过a的取值范围为[1,m+1],b为[0,m-1]而已。
考虑extBSGS里的逆元:(A/g)
我们把这一坨最后归到左边,就没有逆元了吧,然后查表的时候初值设成这个数即可。
这样就很优美了吧
比一直求逆元的bsgs跑的快多了
# include <map> # include <math.h> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; # define RG register # define ST static inline int pwr(int a, int b, int P) { int ret = 1; while(b) { if(b&1) ret = 1ll * ret * a % P; a = 1ll * a * a % P; b >>= 1; } return ret; } map<int, int> mp; inline int BSGS(int A, int B, int P) { } inline int extBSGS(int A, int B, int P) { A %= P, B %= P; if(B == 1) return 0; int cnt = 0, d = 1; for (int g = __gcd(A, P); g!=1; g = __gcd(A, P)) { if(B % g) return -1; P /= g, B /= g; d = 1ll * d * A / g % P; ++cnt; if(B == d) return cnt; } mp.clear(); int m = ceil(sqrt(1.0 * P)), t = B; for (int i=0; i<m; ++i) { mp[t] = i; t = 1ll * t * A % P; } int g = pwr(A, m, P); t = 1ll * d * g % P; for (int i=1; i<=m+1; ++i) { if(mp.count(t)) return cnt + i*m - mp[t]; t = 1ll * t * g % P; } return -1; } int main() { int A, B, P, ans; while(cin >> A >> P >> B && (A+B+P)) { if(P == 1) { puts("0"); continue; } ans = extBSGS(A, B, P); if(ans == -1) puts("No Solution"); else printf("%d\n", ans); } return 0; }
bzoj2480 Spoj3105 Mod