裸的BSGS

安利这个blog，我觉得讲得很靠谱

顺便BSGS真的不用求逆元，既然可以设x=ka+b，不如直接设成x=ka-b，乘到那边就完事了

不用求但是还是要用到逆元的思想

以上

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<map>
#include<set>
using namespace std;	long long B,N,P;
long long mult(long long u,long long v){return (u*v-(long long)((long double)u*v/P)*P+P)%P;
}map<long long,int> mp;
set<long long> stt;long long ans;
long long BSGS(long long a,long long b,long long p){ans=-1;a%=p,b%=p;map<long long,int> mp_tmp;mp_tmp.swap(mp);set<long long> set_tmp;set_tmp.swap(stt); long long root_p=ceil(sqrt((double)p));if(b==1)	return ans=0;long long tmp=1,ttmp;	for(int i=0;i<root_p;++i,tmp=mult(tmp,a),b=mult(b,a))stt.insert(b),mp[b]=i;ttmp=tmp;for(int i=1;i<=root_p;++i,ttmp=mult(ttmp,tmp))if(stt.count(ttmp))return ans=i*root_p-mp[ttmp];return ans;
}int main(){while(~scanf("%lld%lld%lld",&P,&B,&N))(~BSGS(B,N,P))?printf("%lld\n",ans):puts("no solution");return 0;
}