发布时间：2024-09-28

BSGS

BSGS(Baby Step Grant Step)

$a^x \equiv b(mod\ p) 已知a，b求最小非负数x，保证a，p互质$ 欧拉函数：$a^{\phi(p)} \equiv 1(mod\ p)$
因此 $a^t \equiv a^{x \cdot \phi (p)}$
$x范围为[0,\phi(p)-1],分块求解块长k=\lceil \sqrt p \rceil$ 令 $t=kx-y，x∈[1,k]，y∈[0,k-1] ,a^{kx} \equiv b \cdot a^y(mod\ p)$ 先用哈希表存$b \cdot a^y(mod\ p)$的值，再遍历左边

int bsgs(int a,int b,int p){
    if(1%p==b%p)return 0;//特判x=0
    int k=sqrt(p)+1;
    vector<int> pw(k+1);
    unordered_map<int,int> mp;
    pw[0]=1;
    for(int i=1;i<=k;i++)pw[i]=pw[i-1]*a%p;
    for(int i=0;i<k;i++)mp[b*pw[i]%p]=i;
    for(int i=1,j=pw[k];i<=k;i++,j=j*pw[k]%p){
        if(mp.count(j))return k*i-mp[j];
    }
    return -1;
}

exBSGS

• 假设a，p不互质
• $gcd(a,p)=d,a^t \equiv b(mod\ p)等价于a^t+kp=b$
• 如果d不能整除b则无解
• 否则 $\frac{a}{d}a^{t-1} \equiv \frac{b}{d}(mod\ \frac{p}{d})等价于a^{t-1} \equiv \frac{b}{d} \cdot (\frac{a}{d})^{-1} (mod\ \frac{p}{d})$
• 递归求解直至不互质，最多递归log次

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int bsgs(int a,int b,int p){
    if(1%p==b%p)return 0;//特判x=0
    int k=sqrt(p)+1;
    vector<int> pw(k+1);
    unordered_map<int,int> mp;
    pw[0]=1;
    for(int i=1;i<=k;i++)pw[i]=pw[i-1]*a%p;
    for(int i=0;i<k;i++)mp[b*pw[i]%p]=i;
    for(int i=1,j=pw[k];i<=k;i++,j=j*pw[k]%p){
        if(mp.count(j))return k*i-mp[j];
    }
    return -1;
}
int exbsgs(int a,int b,int p){
    b=(b%p+p)%p;//保证正数
    if(1%p==b%p)return 0;
    int x,y;
    int d=exgcd(a,p,x,y);
    if(d>1){
        if(b%d)return -1;
        exgcd(a/d,p/d,x,y);
        int ans=exbsgs(a,b/d*x%(p/d),p/d);
        if(ans==-1)return -1;
        return ans+1;
    }
    return bsgs(a,b,p);
}

P3306 [SDOI2013] 随机数生成器

题意： $第i天看的数是x_i$$x_{i+1}=(x_i \times a + b)(mod\ p)$
通向公式：$x_n+\frac{b}{a-1}=a^{n-1}(x_1+\frac{b}{a-1})(mod\ p)$
$x_n=t,a^{n-1}=\frac{t+\frac{b}{a-1}}{x_1+\frac{b}{a-1}}(mod\ p)$

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int bsgs(int a,int b,int p){
    if(1%p==b%p)return 0;//特判x=0
    int k=sqrt(p)+1;
    vector<int> pw(k+1);
    unordered_map<int,int> mp;
    pw[0]=1;
    for(int i=1;i<=k;i++)pw[i]=pw[i-1]*a%p;
    for(int i=0;i<k;i++)mp[b*pw[i]%p]=i;
    for(int i=1,j=pw[k];i<=k;i++,j=j*pw[k]%p){
        if(mp.count(j))return k*i-mp[j];
    }
    return -1;
}
int exbsgs(int a,int b,int p){
    b=(b%p+p)%p;//保证正数
    if(1%p==b%p)return 0;
    int x,y;
    int d=exgcd(a,p,x,y);
    if(d>1){
        if(b%d)return -1;
        exgcd(a/d,p/d,x,y);
        int ans=exbsgs(a,b/d*x%(p/d),p/d);
        if(ans==-1)return -1;
        return ans+1;
    }
    return bsgs(a,b,p);
}
int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}
int inv(int a,int p){
    int x,y;
    exgcd(a,p,x,y);
    x=(x%p+p)%p;
    return x;
}
void solve(){
    int p,a,b,x,t;
    cin>>p>>a>>b>>x>>t;
    if(x==t){
        cout<<"1\n";
        return;
    }
    if(a==0){
        if(b==t)cout<<"2\n";
        else cout<<"-1\n";
        return;
    }
    if(a==1){
        if(b==0)cout<<"-1\n";
        else{
            cout<<((t-x)%p+p)%p*inv(b,p)%p+1<<"\n";
        }
        return;
    }
    int C=b*inv(a-1,p)%p;
    int A=(x+C)%p;
    int B=(t+C)%p;
    int res=exbsgs(a,B*inv(A,p)%p,p);
    if(res==-1)cout<<res<<"\n";
    else cout<<res+1<<'\n';
}