原题链接： P4195 【模板】扩展 BSGS/exBSGS

加强的#11是一个顽强的数据点！！！泰玄辣！！！

先是用$unordered\_map$ TLE on #11,然后改成$map$就AC了

进入讨论版发现很多dalao都是把$map$改成$unordered_\_map$才能过。。。

但是$unordered\_map$不是要比$map$更快吗？？？

AC代码：

#include<bits/stdc++.h> 
#include<unordered_map>
#include<map>
using namespace std;
template< typename T > inline void read(T &x){
	char c=getchar();x=0;int f=0;
	for(;!isdigit(c);c=getchar()) f|=(c=='-');
	for(;isdigit(c);c=getchar()) x=((x<<3)+(x<<1)+(c^48));
	x=f?-x:x;
}
template< typename T > inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
typedef long long LL;

const int INF=0x3f3f3f3f;
int a,b,p;
map<int,int> hs;
int exgcd(int a,int b,int &x,int &y) {
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int BSGS(int a,int b,int p) {
    if (1%p==b%p) return 0;
    int k=sqrt(p)+1;
    hs.clear();
    for(int y=0,r=b%p;y<k;y++) {
        hs[r]=y;
        r=(LL)r*a%p;
    }
    int ak=1;
    for(int i=1;i<=k;i++) ak=(LL)ak*a%p;
    for (int x=1,l=ak;x<=k;x++) {
        if (hs.count(l)) return k*x-hs[l];
        l=(LL)l*ak%p;
    }
    return -INF;
}

int exBSGS(int a, int b, int p) {
    b=(b%p+p)%p;
    if(1%p==b%p) return 0;
    int x,y;
    int d=exgcd(a,p,x,y);
    if(d>1){
        if (b%d) return -INF;
        exgcd(a/d,p/d,x,y);
        return exBSGS(a,(LL)b/d*x%(p/d),p/d)+1;
    }
    return BSGS(a,b,p);
}
int main() {
	// freopen("bsgs.in","r",stdin);
	// freopen("bsgs.out","w",stdout);
	int T;
	// scanf("%d",&T);
	while(1){
		read(a);read(p);read(b);
        if(a==0&&p==0&&b==0){
            return 0;
        }
		int res=exBSGS(a,b,p);
        if(res<0) puts("No Solution");
        else write(res),puts("");
	}
    return 0;
}