引入

P3846 [TJOI2007] 可爱的质数/【模板】BSGS

给定一个质数 p p p 以及整数 a 、 b a、b a、b

你需要给出最小的非负整数 x x x，满足：

a x ≡ b ( m o d p ) a^x\equiv b\pmod p ax≡b(modp)

或输出无解。
2 ≤ a , b < p < 2 31 2\le a,b<p<2^{31} 2≤a,b<p<231

BSGS

全称为 B a b y S t e p G i a n t S t e p Baby\ Step\ Giant\ Step Baby Step Giant Step，简称BSGS或者北上广深算法。

怎么做呢？其实本质是枚举
最原始的做法：暴力枚举 x ∈ [ 0 , p ) x\in[0,p) x∈[0,p) 然后检验答案是否正确。
优化，我们可以考虑折半枚举。

我们令 x = k n + i x=kn+i x=kn+i，这里 n n n 是我们设的一个定值， k 、 i k、i k、i 都为变量。

这样，原式变成： a k n + i ≡ b ( m o d p ) a^{kn+i}\equiv b\pmod p akn+i≡b(modp)

由于 gcd ⁡ ( a , p ) = 1 \gcd(a,p)=1 gcd(a,p)=1，我们转移一下变成： a k n ≡ b ( a i ) − 1 ( m o d p ) a^{kn}\equiv b(a^i)^{-1}\pmod p akn≡b(ai)−1(modp)
我们可以枚举所有的 i i i ，将右边的值存入哈希表。

然后枚举 k k k 的过程中，去表中找满足的 i i i，找到后 k n + i kn+i kn+i 就是答案。
那么 n n n 的设置，就像分块思想一样，我们设为 p \sqrt p p

，这样 k 、 i k、i k、i 都只用枚举到 p \sqrt p p

代码

时间复杂度： O ( p ) O(\sqrt p) O(p

)

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}

const int MAX = 30;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;

ll qpow(ll a,ll n,ll p){a%=p;ll res = 1LL;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll exgcd(ll a,ll b,ll& x,ll& y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    ll ans = exgcd(b,a%b,x,y);
    ll tmp = x;
    x = y;
    y = tmp - a/b*y;
    return ans;
}
ll inv(ll a,ll mod){
    ll x,y;
    ll g = exgcd(a,mod,x,y);
    if(g!=1)return -1;
    return (x%mod+mod)%mod;
}
ll BSGS(ll a,ll b,ll p){
    b%=p;
    if(b==1||p==1)return 0;
    ll n = sqrt(p);
    unordered_map<ll,ll>M;
    ll inva = inv(qpow(a,n-1,p),p) * b % p;
    for(ll i = n-1;~i;--i){
        M[inva] = i;
        inva = inva * a % p;
    }
    ll ta = 1,powa = qpow(a,n,p);
    for(ll k = 0;k <= p;k+=n){
        if(M.count(ta))return k + M[ta];
        ta = ta * powa % p;
    }
    return -1;
}
int main()
{
    ll p,b,n,ans;
    cin >> p >> b >> n;
    ans = BSGS(b,n,p);
    if(ans == -1)puts("no solution");
    else cout << ans;
    return 0;
}

扩展BSGS

P4195 【模板】扩展 BSGS/exBSGS

给定整数 a 、 b 、 p a、b、p a、b、p

你需要给出最小的非负整数 x x x，满足：

a x ≡ b ( m o d p ) a^x\equiv b\pmod p ax≡b(modp)

或输出无解。
1 ≤ a , b , p < 1 0 9 1\le a,b,p<10^9 1≤a,b,p<109

ExBSGS

因为 gcd ⁡ ( a , p ) ≠ 1 \gcd(a,p)\ne 1 gcd(a,p)=1，所以不能像原来一样使用逆元了。

所以我们想把 g c d gcd gcd 先提出来。我们令 d = gcd ⁡ ( a , p ) d=\gcd(a,p) d=gcd(a,p)
我们把原式 a x ≡ b ( m o d p ) a^x\equiv b\pmod p ax≡b(modp) 展开成 a x + k p = b a^x+kp=b ax+kp=b

两边同时除以 d d d，变成 a x d + k p d = b d \frac{a^x}{d}+k\frac{p}{d}=\frac{b}{d} dax+kdp=db

取模，得到： a x d ≡ b d ( m o d p d ) \frac{a^x}{d}\equiv \frac{b}{d}\pmod {\frac{p}{d}} dax≡db(moddp)

发现， b b b 必须是 d d d 的倍数，否则直接返回无解。

此时 gcd ⁡ ( a d , p d ) = 1 \gcd(\frac{a}{d},\frac{p}{d})=1 gcd(da,dp)=1，所以就可以乘上它的逆元

变成： a x − 1 ≡ b d ( a d ) − 1 ( m o d p d ) a^{x-1}\equiv \frac{b}{d}(\frac{a}{d})^{-1}\pmod {\frac{p}{d}} ax−1≡db(da)−1(moddp)

然后就变成了一个新的问题。但是此时 gcd ⁡ ( a , p d ) \gcd(a,\frac{p}{d}) gcd(a,dp) 不一定为 1 1 1，可以递归处理。（当然也可以不递归处理）
注意就是BSGS里面的 u n o r d e r e d _ m a p unordered\_map unordered_map 改成 m a p map map 在这道题里会快很多，因为出题人特意卡了一个样例…

递归版代码

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}

const int MAX = 30;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;

ll qpow(ll a,ll n,ll p){a%=p;ll res = 1LL;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll exgcd(ll a,ll b,ll& x,ll& y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    ll ans = exgcd(b,a%b,x,y);
    ll tmp = x;
    x = y;
    y = tmp - a/b*y;
    return ans;
}
ll inv(ll a,ll mod){
    ll x,y;
    ll g = exgcd(a,mod,x,y);
    if(g!=1)return -1;
    return (x%mod+mod)%mod;
}
ll BSGS(ll a,ll b,ll p){
    b%=p;
    if(b==1||p==1)return 0;
    ll n = sqrt(p);
    unordered_map<ll,ll>M;
    ll inva = inv(qpow(a,n-1,p),p) * b % p;
    for(ll i = n-1;~i;--i){
        M[inva] = i;
        inva = inva * a % p;
    }
    ll ta = 1,powa = qpow(a,n,p);
    for(ll k = 0;k <= p;k+=n){
        if(M.count(ta))return k + M[ta];
        ta = ta * powa % p;
    }
    return -1;
}
ll ExBSGS(ll a,ll b,ll p){
    b%=p;
    if(a==0 && b==0)return 1;
    if(a==0 && b!=0)return -1;
    if(b==1||p==1)return 0;
    ll d = __gcd(a,p);
    if(b%d!=0)return -1;
    p/=d;
    b=b/d*inv(a/d,p)%p;
    if(d!=1){
        ll ans = ExBSGS(a,b,p);
        if(ans==-1)return -1;
        return ans+1;
    }
    ll ans = BSGS(a,b,p);
    if(ans == -1)return -1;
    return ans+1;
}
int main()
{
    ll a,b,p,ans;
    while(~scanf("%lld%lld%lld",&a,&p,&b)){
        if(p == 0)break;
        ans = ExBSGS(a,b,p);
        if(ans == -1)puts("No Solution");
        else printf("%lld\n",ans);
    }

    return 0;
}

非递归版

ll ExBSGS(ll a,ll b,ll p){
    b%=p;
    if (b==1||p==1)return 0;
    int 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);
    }
    int f=BSGS(a,b*inv(na,p)%p,p);
    if (f==-1)return -1;
    return f+k;
}

【算法讲25：BSGS】BSGS与扩展BSGS引入BSGS代码扩展BSGSExBSGS递归版代码非递归版

【算法讲25：BSGS】

引入

BSGS

代码

扩展BSGS

ExBSGS

递归版代码

非递归版

继续阅读

HDU 1222（Wolf and Rabbit）

hdu 2582

hdu 1145

Hdu4405 Aeroplane chess 数论

HDU 1452 Happy 2004 (因子和)Happy 2004

hdu3073 Lucas定理

中国剩余定理(CRT)：求解模线性方程组

CodeForces - 1459C Row GCD (思维+数学)Row GCD

使序列有序的最少交换次数

bzoj 4659: Lcm （反演）

BZOJ3643 Phi的反函数（数论+搜索）

hdu 1286 找新朋友（欧拉函数）

HDOJ 1286 找新朋友找新朋友

【多项式】拉格朗日插值

D. Dreamoon and Sets(构造+数论)

POJ 1284 Primitive Roots (欧拉函数&原根定理)