P4195 【模板】扩展 BSGS/exBSGS

求解：，不一定互质。

如果，则存在逆元，直接使用求解。

具体的，假设，如果，方程无解。否则，方程同时除以：

直到

记，于是方程变成：

套时，没必要计算出的逆元然后挪到等式右边，只需要在枚举时查找是否存在即可。

注意，不排除小于等于的情况，也就是可能说在还没有达到时就有解了，这个需要特判。

这题卡常，需要用比较快的哈希板子。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1<<16)-1;
struct HASH{
    int v[maxn+1],tot,ed=0;
    struct node{
        int t,p,next;
    }a[maxn<<1];
    void ins(int x,int y) {
        int k=x&maxn;
        if(v[k]!=ed) {
            v[k]=ed;
            a[k].t=x,a[k].p=y,a[k].next=0;
        }
        else {
            for(;;k=a[k].next) {
                if(a[k].t==x) return a[k].p=y,void();
                if(!a[k].next) break;
            }
            a[k].next=++tot,a[tot].t=x,a[tot].p=y,a[tot].next=0;
        }
    }
    int find(int x) {
        int k=x&maxn;
        if(v[k]!=ed) return -1;
        for(;;k=a[k].next)
            if(a[k].t==x) return a[k].p;
            else if(!a[k].next) return -1;
    }
}mp;
int gcd(int a,int b) {
    if(!b) return a;
    while((a%=b) && (b%=a));
    return a+b;
}
int bsgs(int a,int b,int p,int na) {
    if(!a) {
        if(!b) return 1;
        else return -1;
    }
    if(b==na||p==1) return 0;
    mp.tot=maxn;
    int m=ceil(sqrt(p));
    ll tmp=1,s=na;
    for(int j=0; j<m; ++j)
        mp.ins(tmp*b%p,j),tmp=tmp*a%p;
    for(int i=1; i<=m; ++i) {
        s=s*tmp%p;
        if(~mp.find(s)) return i*m-mp.find(s);
    }
    return -1;
}
int exbsgs(int a,int b,int p) {
    if(b==1||p==1) return 0;
    int g=gcd(a,p),k=0,na=1;
    while(g>1) {
        if(b/g*g!=b) return -1;
        ++k,p/=g,b/=g,na=1LL*na*(a/g)%p,g=gcd(a,p);
        if(na==b) return k;
    }
    int x,y,res;
    res=bsgs(a,b,p,na);
    if(res==-1) return -1;
    else return res+k;
}
signed main() {
    cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
    int a,p,b;
    while(cin>>a>>p>>b) {
        if(!a&&!p&&!b) return 0;
        a%=p,b%=p,++mp.ed;
        int x=exbsgs(a,b,p);
        if(~x) cout<<x<<'\n';
        else cout<<"No Solution\n";
    }
    return 0;
}