浅谈gcd,BSGS

1. $\gcd$¿$\gcd$¡

   众所周知两个整数$A$和$B$可以表示为$A=am,B=bm,$其中$a,b$互质。

   那么$m=\gcd(A,B)$，也就是$A$和$B$的最大公约数。

   这里有一个$m$的定义式（其中$f(A,B)$表示$\gcd(|A|,|B|)$）：
   $m=\begin{cases}f(A,B)&A<0\text{并且}B>0\\f(A,B)&A>0\text{并且}B<0\\f(A,B)&A>0,B>0\\0&A=B=0\\|A|&B=0\text{并且}A\ne 0\\|B|&A=0\text{并且}B\ne 0\end{cases}$

   那么，我们的中心就是转移到了求$f(A,B)$上面。

   这里先上结论：
   $f(A,B)=\begin{cases}f(B,A\bmod B)&B\ne 0\\A&B=0\end{cases}$

   证明：

   $f(A,B)=f(m,m)=f(mb,km(a-b))=f(b,a-kb)=f(b,a\bmod b)$。

   那好，那么代码实现就极其容易了，如下：

   ll gcd(ll a,ll b){
       if(b) return gcd(b,a%b);
       return abs(a);
   }
   

2. $ax+by=\gcd(a,b)=m$

   不定方程。

   此处设$m=\gcd(a,b)$。

   题目要求求$ax+by=m(x\in \mathbb{Z},a,b>0)$中，$x$的最小值。

   假设一组解$x_2,y_2$满足$bx_2+(a\bmod b)y_2=m$。

   那么，我们就能得出：$ax+by=ax_2+by_2$。

   现在，求出$x,y$就是我们的唯一目标。

   但是，此处求出最小解，就犹如大海捞针，我们需要一步步来，先求出一组可能的解。

   于是，我们想到了取模的定义。

   $a\bmod b=a-b\times s(\frac ab)$，其中$s(x)$表示$x$向下取整。

   所以：
   $ax+by=bx_2+(a-b\times s(\frac ab))y_2=bx_2+ay_2-b\times s(\frac ab)y_2$

   $bx_2+ay_2-b\times s(\frac ab)y_2=ay_2+b(x_2-s(\frac ab)y_2)$

   也就是说，利用小学数学，我们可以得到：

   $a(x-y_2)+b(y-x_2+s(\frac ab)y_2)=0$

   但是$x,y\ne 0$，所以，命中注定的一组解已经写下：

   $x=y_2,y=x_2-s(\frac ab)y_2$

   那么，怎么求$x_2,y_2$呢？

   我们列出和$x_2,y_2$有关的式子。

   $bx_2+(a\bmod b)y_2=m$

   然后发现，除了系数的改变，我们啥都没改，一切都和原来的一样。

   然后，我脱口而出：

   我们需要一个$x_3$，一个$y_3$，使得$(b\bmod (a\bmod b))y_3+(a\bmod b)x_3=m$。

   天哪，这不就是$\gcd$吗？

   于是，我们就可以到达最极端的那头：

   $mx_n=m,x_n=1,y_n=0$。

   然后就可以一层一层求出这个解了（虽然不是最小的）。

   代码：

   inline ll exgcd(ll &x,ll &y,ll a,ll b){
       if(b==0){
           x=1;y=0;
           return a;
       }
       ll dl=exgcd(x,y,b,a%b);
       int z=x;
       x=y;
       y=z-y*(a/b);
       return dl;
   }
   

3. 快速幂

   ull ksm(ull a,ull b){
       ull ans = 1,base=a;
       while(b){
           if(b&1){
               ans*=base;
            }
            base*=base;
            b>>=1;
        }
        return ans;
   }
   

   大致思路：先把$b$拆成二进制形式，每次查看最后一位，如果是$1$的话就乘上$base$，是$0$就不管它，而对于每一轮，$base$同时变成平方，而最初时$base=a$，表示$a^1$

   初始化要设成$1$，因为$\forall x\ne 0$有$x^0=1$

   代码这么短背一背就行了

4. BSGS

   这个方法用于解方程$a^x\equiv b\pmod p$。

   假设$x=im-j,m=c(\sqrt{p})(c$是向上取整$)$。

   所以就有$a^{im}\equiv ba_j\pmod p$。

   然后我们需要枚举$ba^j$，存到hash表里边。

   接下来就是枚举$i(1\ to\ m)$直到满足$a^{im}\equiv ba^j\pmod p$。

   如果存在的话那么此处$i$肯定是最小的。

   代码：

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int N=100001,inf=0x7f7f7f7f;
map<ll,int>mp;
ll p,a,b,n,m,now,ans,t;
bool flag;
ll ksm(ll a,ll b){
    ll ans=1,base=a;
    while(b){
        if(b&1){
            ans*=base;
            ans%=p;
        }
        base*=base;
        base%=p;
        b>>=1;
    }
    return ans%p;
}
int main(){
    cin>>p>>b>>n;
    if(b%p==0){
        cout<<"no solution";
        return 0;
    }
    m=ceil(sqrt(p));
    mp[n%p]=0;
    fs(i,1,m,1){
        mp[ksm(b,i)*n%p]=i;
    }
    t=ksm(b,m);
    now=1;
    fs(i,1,m,1){
        now=(now*t)%p;
        if(mp[now]){
            flag=1;
            ans=i*m-mp[now];
            cout<<(ans%p+p)%p; 
            return 0;
       }
    }
    cout<<"no solution";
    return 0;
}