BSGS算法 || POJ2417 || luogu P3846

吐了。。。写完poj2417之后意识到poj不支持stl和__int128。。。你好歹是个大学的软件，不管你们acmer的吗。。

鬼才写快速乘和hash。不让我用__int128和map我就不交poj上了。发现luogu有一模一样的板子题。

题目：P3846 [TJOI2007] 可爱的质数/【模板】BSGS

题意：

讲一下bsgs算法。bsgs算法的思路是，既然答案要求L，设m为sqrt(P），则可将L表示为km-j（其中0<=k，j<=m,且 km-j>=0 ）。

（由费马小定理可知若存在L，L必小于P。）则原式转化为B^km=N×B^j。原问题转化为找出该方程的一组解，并且使得L=km-j最小。

大学生（可以公然使用STL的人上人）的做法是：预处理出N×B^j（mod P）的值，并且用map记录此时的 j 值。然后从0到m枚举k，

只要满足上式且km-j>=0即可的出答案。注意bsgs不能处理余数为0的情况。

由于虽然对P取模，但是两个long long相乘仍可能炸long long，所以大部分bsgs题目需要一些处理。苦逼高中生的做法是快速乘。

快乐大学生的做法是直接用(__int128)暂时存储相乘后的结果，取模后再强制转化回long long类型。

其实可以不用快速幂，luogu上测了199ms；用了快速幂后是366ms。因为单次快速幂是log的，本来很快，但是bsgs问题P太大了。

bsgs算法时间复杂度约为O(sqrt(P))。

代码：

不使用快速幂：

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 ll p,b,n;
 5 map<ll,int>mp;
 6 /*inline ll ksm(ll a,ll b,ll p){
 7     ll res=1;
 8     while(b){
 9         if(b&1)res=(__int128)res*a%p;
10         a=(__int128)a*a%p;
11         b>>=1;
12     }
13     return res;
14 }*/
15 ll bsgs(ll p,ll b,ll n){
16     mp.clear();
17     ll m=pow(p,0.5)+1,cf=1;
18     for(int i=0;i<=m;i++){
19         if(i!=0) cf=(__int128)cf*b%p;
20         else cf=1;
21         mp[(__int128)cf*n%p]=i;
22     }
23     b=cf;
24     for(int i=0;i<=m;i++){
25         if(i) cf=(__int128)cf*b%p;else cf=1;
26         if(mp.find(cf)!=mp.end()){
27             int j=mp[cf];
28             if(i*m-j>=0) return i*m-j;
29         }
30     }
31     return -1;
32 }
33 int main(){
34     while(~scanf("%lld%lld%lld",&p,&b,&n)){
35         if(n!=0){
36             ll ans=bsgs(p,b,n);
37             if(ans!=-1) printf("%lld/n",ans);
38             else puts("no solution");
39         }
40         // bsgs 不能处理整除的情况。但是这道题不涉及。 
41     }
42     return 0;
43 }

View Code

使用快速幂：

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 ll p,b,n;
 5 map<ll,int>mp;
 6 inline ll ksm(ll a,ll b,ll p){
 7     ll res=1;
 8     while(b){
 9         if(b&1)res=(__int128)res*a%p;
10         a=(__int128)a*a%p;
11         b>>=1;
12     }
13     return res;
14 }
15 ll bsgs(ll p,ll b,ll n){
16     mp.clear();
17     ll m=pow(p,0.5)+1,cf=1;
18     for(int i=0;i<=m;i++){
19         cf=ksm(b,i,p);
20         mp[(__int128)cf*n%p]=i;
21     }
22     b=ksm(b,m,p);
23     for(int i=0;i<=m;i++){
24         cf=ksm(b,i,p);
25         if(mp.find(cf)!=mp.end()){
26             int j=mp[cf];
27             if(i*m-j>=0) return i*m-j;
28         }
29     }
30     return -1;
31 }
32 int main(){
33     while(~scanf("%lld%lld%lld",&p,&b,&n)){
34         if(n!=0){
35             ll ans=bsgs(p,b,n);
36             if(ans!=-1) printf("%lld/n",ans);
37             else puts("no solution");
38         }
39         // bsgs 不能处理整除的情况。但是这道题不涉及。 
40     }
41     return 0;
42 }

View Code

By:AlenaNuna