P4195 TLE #11

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
#include <unordered_map>
#define int long long
using namespace std;
int a,p,b;
unordered_map <int,int> f;
int gcd(int a,int b)     //最大公约数
{
    if (!b)return a;
    return gcd(b,a%b);
}
void exgcd(int a,int b,int &x,int &y)  //扩欧
{
	if (!b)x=1,y=0;
	else
	{
		exgcd(b,a%b,x,y);
		int t=x;
		x=y;
		y=t-a/b*y;
	}
}
int inv(int a,int b)    //逆元
{
	int x,y;
	exgcd(a,b,x,y);
	return (x%b+b)%b;
}
int mypow(int a,int x,int p)
{
    int s=1;
    while (x)
    {
        if (x&1)s=s*a%p;
        a=a*a%p;
        x>>=1;
    }
    return s;
}
int bsgs(int a,int b,int p)    //BSGS算法
{
    f.clear();
    int m=ceil(sqrt(p));
    b%=p;
    for (int i=1;i<=m;i++)
    {
        b=b*a%p;
        f[b]=i;
    }
    int tmp=mypow(a,m,p);
    b=1;
    for (int i=1;i<=m;i++)
    {
        b=b*tmp%p;
        if (f[b])return (i*m-f[b]+p)%p;
    }
    return -1;
}
int exbsgs(int a,int b,int p)
{
    if (b==1||p==1)return 0;     //特殊情况，x=0时最小解
    int g=gcd(a,p),k=0,na=1;
    while (g>1)
    {
        if (b%g!=0)return -1;    //无法整除则无解
        k++;b/=g;p/=g;na=na*(a/g)%p;
    	if (na==b)return k;   //na=b说明前面的a的次数为0，只需要返回k
    	g=gcd(a,p);
    }
    int f=bsgs(a,b*inv(na,p)%p,p);
    if (f==-1)return -1;
    return f+k;
}
signed main()
{
//    cin>>a>>p>>b;
	scanf("%d%d%d", &a, &p, &b);
    while(a||b||p)
    {
    	a%=p;b%=p;
        int t=exbsgs(a,b,p);
//        if (t==-1)cout<<"No Solution"<<endl;
//        else cout<<t<<endl;
//        cin>>a>>p>>b;
		if (t==-1)printf("No Solution\n");
		else printf("%d\n", t);
		scanf("%d%d%d", &a, &p, &b);
    }
    return 0;
}
/*测试tj时间复杂度，绝对不是copy*/