1.BSGS

求解如关于$x$的方程$A^x≡B \mod\ p$ 的最小整数解。$(A,p互质,p为质数)$

不难发现$x<=p$ 因为会出现循环。

靠虑将$x$分解为$i\times sqrt(p)-j$ 。

则原式化为$A^{i\times \lceil sqrt(p)\rceil}\times A^{-j}≡B \mod\ p$

对$A^{-j}$求逆元得$A^{i\times \lceil sqrt(p)\rceil}≡B\times A^j \mod\ p$

因为可以求一个同余方程$A^{-j}\times inv_{A^{-j}}≡1\ mod\ p$

显而易见$inv_{A^{-j}}$即为$A^j$ ,其实有点像移项，可惜$p$不与$A$互质移不过来，可能导致左边$mod\ p$后为$0$

然后可知在$mod\ p$的意义下左右两式相等。

所以就可以用$map$把左右的值映射成它的指数，先做右边($j$从$0$枚举到$\lceil sqrt(p)\rceil$),并把每次的$j$映射到$map$以$B\times A^j$为下标的空间中。然后做左边($i$从$1$枚举到$ \lceil sqrt(p)\rceil$)，每次查表搞一搞，第一次遇到相同的值就可以拿现在的$i\times \lceil sqrt(p)\rceil$与表中的$j$相减即为最小值，因为此时$i\times \lceil sqrt(p)\rceil$最小，$j$最大。

理论时间复杂度为$O(sqrt(p))$,但由于用了$map$所以多了红黑树查值的复杂度，所以多了个$log$。

代码

#include<bits/stdc++.h>
using namespace std;
long long b,p,a;
void Read(long long &x)
{
    long long f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
long long KSM(long long base,long long index,long long p)
{
    long long Res=1;
    while (index)
    {
        if (index%2==1) Res*=base,Res%=p;
        base*=base;
        base%=p;
        index/=2;   
    } 
    return Res%p;
}
long long BSGS(long long a,long long b,long long p)
{
    map <long long,long long> m;
    long long X=(long long)ceil(sqrt(p));
    m[b]=0;
    long long Ans_=b;
    for (int i=1;i<=X;i++) Ans_*=a,Ans_%=p,m[Ans_]=i;
    long long Ans__=KSM(a,X,p);
    long long Ans___=1,Ans=-1;
    for (int i=1;i<=X;i++) 
    {
        Ans___*=Ans__,Ans___%=p;
        if (m.count(Ans___)) {Ans=i*X-m[Ans___];break;}
    }
    return Ans;
}
int main() 
{
    Read(p),Read(a),Read(b);
    long long answer=BSGS(a,b,p);
    if (answer==-1) cout<<"no solution"<<endl;
    else cout<<answer<<endl;
    return 0;
}

2.exBSGS

若$A,p$不互质，那普通的$BSGS$就难以胜任了，所以需要使用$exBSGS$

其实也很简单，假设$t=gcd(A,p)$,则可推出$A^{x-1}\times \frac{A}{t}≡\frac{B}{t} \mod p$

若$t\nmid B$,则只有$B=1$时有$x=0$的最小解

若$t \mid b $,则当$t=1$时用$BSGS$,求解即可。

反复执行，直至$A,p$互质。

最后，若此过程需要反复进行$k$次,则答案为$BSGS$的解$x+k$。

代码

#include<bits/stdc++.h>
using namespace std;
long long b,p,a;
void Read(long long &x)
{
    long long f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
long long gcd(long long a,long long b)
{
    if (b==0) return a;
    return gcd(b,a%b);
}
long long KSM(long long base,long long index,long long p)
{
    long long Res=1;
    while (index)
    {
        if (index%2==1) Res*=base,Res%=p;
        base*=base;
        base%=p;
        index/=2;   
    } 
    return Res%p;
}
void ex_gcd(long long a,long long b,long long &d,long long &x,long long &y) {
    if (b==0) x=1,y=0,d=a;
    else    
    {
        ex_gcd(b,a%b,d,x,y);
        long long tmp=x;x=y;y=tmp-a/b*y;
    }
}
long long inv(long long a,long long b)
{
    long long x,y,d;
    ex_gcd(a,b,d,x,y);
    return (x%b+b)%b;
}
long long BSGS(long long a,long long b,long long p)
{
    map <long long,long long> m;
    long long X=(long long)ceil(sqrt(p));
    m[b]=0;
    long long Ans_=b;
    for (int i=1;i<=X;i++) Ans_*=a,Ans_%=p,m[Ans_]=i;
    long long Ans__=KSM(a,X,p);
    long long Ans___=1,Ans=-1;
    for (int i=1;i<=X;i++) 
    {
        Ans___*=Ans__,Ans___%=p;
        if (m.count(Ans___)) {Ans=i*X-m[Ans___];break;}
    }
    return Ans;
}
long long exBSGS(long long a,long long b,long long p)
{
    if (b==1||p==1)return 0;     
    long long 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;   
        g=gcd(a,p); 
    }
    long long f=BSGS(a%p,b*inv(na,p)%p,p);
    if (f==-1)return -1;
    return f+k;
}

int main() 
{
    while (1)
    {
    Read(a),Read(p),Read(b);
    if (p==0||a==0||b==0) break;
    long long answer=exBSGS(a,b,p);
    if (answer==-1) cout<<"No Solution"<<endl;
    else cout<<answer<<endl;
    }
    return 0;
}