# 大步小步()-其他

## 大步小步()

(这里设总块数为 $$i$$，零散块为 $$j$$，块长为 $$t$$

EX-BSGS

#include <iostream>
#include <map>
#define ll long long

using namespace std;
ll a,b,p;
map<ll,ll>hsh;

void bsgs(){
ll t;
for(t=1;t*t<=p;++t) ;
--t;
ll tmp=1;
hsh[0]=b;
for(int i=1;i<t;++i)
tmp=(tmp*a)%p,hsh[(b*tmp)%p]=i;
if(a==0){
if(b==0) cout << 1  << endl;
else cout << "no solution" << endl;
return ;
}
tmp=(tmp*a)%p;
ll q=1;
for(int i=1;i<=t;++i){
q=(tmp*q)%p;
if(hsh.find(q)!=hsh.end()) {
cout << i*t-hsh[q] << endl;
return ;
}
}
cout << "no solution" << endl;

}

signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> p >> a >> b;
bsgs();

return 0;
}


————————

(这里设总块数为 $$i$$，零散块为 $$j$$，块长为 $$t$$

EX-BSGS

#include <iostream>
#include <map>
#define ll long long

using namespace std;
ll a,b,p;
map<ll,ll>hsh;

void bsgs(){
ll t;
for(t=1;t*t<=p;++t) ;
--t;
ll tmp=1;
hsh[0]=b;
for(int i=1;i<t;++i)
tmp=(tmp*a)%p,hsh[(b*tmp)%p]=i;
if(a==0){
if(b==0) cout << 1  << endl;
else cout << "no solution" << endl;
return ;
}
tmp=(tmp*a)%p;
ll q=1;
for(int i=1;i<=t;++i){
q=(tmp*q)%p;
if(hsh.find(q)!=hsh.end()) {
cout << i*t-hsh[q] << endl;
return ;
}
}
cout << "no solution" << endl;

}

signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> p >> a >> b;
bsgs();

return 0;
}