帮你调了一下,中间用快速幂和扩欧帮你优化了一下(调试的代码我没删,可以再调试一下)。但是原题貌似用map过不去。。。用hash能过,用map就看你能优化的程度了
```
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1e18
#define pii pair<int,int>
using namespace std;
typedef long long ll;
inline ll rd(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
ll sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
const int N=1e5+10;
inline void write(ll x){
if (x < 0) {x = ~(x - 1); putchar('-');}
if (x > 9) write(x / 10);
putchar(x % 10 ^ 48);
}
void writes(ll x){write(x), putchar(' ');}
void writen(ll x){write(x), puts("");}
map<ll,int>mp;
void exgcd(ll A, ll B, ll &x, ll &y){
if (! B) x = 1, y = 0;
else {
exgcd(B, A % B, y, x);
ll t = x;
y -= A / B * x;
}
}
ll qpow(ll a, ll y, ll p){
ll res = 1, x = a;
while (y){
if (y & 1) res = res * x % p;
x = x * x % p;
y >>= 1;
}
return res;
}
ll exbsgs(ll a,ll b,ll p){
if (b == 1 || p == 1) return 0;
a%=p,b%=p;
mp.clear();
ll a1=1,nm=0,g=__gcd(a,p);
// printf("%d=%d mod %d %d %d\n",a,b,p,a1,nm);
while(g > 1){
// writen(nm);
a1=a1*(a/g)%p;
if(b%g!=0)return inf;
b/=g;p=p/g;
if (a1 == b) return nm;
g=__gcd(a,p);
nm++;
}
// puts("---");
// writen(a1);
ll x, y;
exgcd(a1, p, x, y);
x = (x % p + p) % p;
b = b * x % p;
// writen(b);
ll up=ceil(sqrt(p));
for(ll i=0,j=b%p;i<=up;i++,j=j*a%p){
mp[j]=i;
}
ll k=qpow(a, up, p), j = 1;
for(ll i=1;i<=up;i++){
// writen(i);
j=j*k%p;
if(mp[j]){
return (((i * up - mp[j] + p) % p) + nm) % p;
}
}
return inf;
}
int main(){
ll a,b,p;
while((a=rd())+(p=rd())+(b=rd())!=0){
ll res=exbsgs(a,b,p);
if(res>=inf)puts("No Solution");
else printf("%lld\n",res);
}
return 0;
}
```
by 似嫩 @ 2021-10-15 12:33:21