数论 BSGS和exBSGS

1.1 BSGS简介

(BSGS)，全称(baby-step-giant-step)，一个解决特定的高次方程的算法。其实与其称作"算法"，个人感觉叫作"思想"更合适ˋ( ° ▽、° )

虽说是"高次同佘方程"，其实特指形如下式的方程:

1.2 尝试解决——暴力大法

首先，根据“费马小定理”：

以及“常识”：

通过两者可知：(a^i quad iin [1,p-1])必定取遍了(a^x)能取到的所有数。存在于否，直接枚举代入一遍即可得知。

for(int i=1;i<=p-1;++i) if(check(i)) ans=i;

1.3 暴力的改进——分块优化

对，正如标题所示，BSGS其实就是分块的应用。

为了方便叙述，设(t=sqrt n),那么(x)可以分解成：(x=itimes t - j)，其中(1leq ileq t),(1leq j < q).可以发现这样分解可以覆盖到所有的(xin [1,p-1])

上式成立的充要条件便是下式成立，于是问题便进一步转化：询问是否有这种((i,j) leq t)，满足：

但是只是单纯枚举(i)和(j)的话，显然复杂度依旧不正确(O(ttimes t=p))

其实到了这一步，(i)和(j)之间已经没有太大的联系了，两者只是有一个共同的范围作限制。因此我们分别枚举(i)和(j)，将出现过的数字记录下来。倘若有一个数字出现了两次，就说明存在一对((i,j))满足条件，进言之，就是存在(itimes t -j Rightarrow x)满足条件。

一个小技巧是:先枚举并记录(j)，后用(i)去判重复。因为此时找到的第一个(i)即对应着最小的(x)，类似于"t进制“的思想。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lor(a,b,c) for(register int a=b;a<=c;++a)
#define ror(a,b,c) for(register int a=c;a>=b;--a)

ll p,b,n,t,ans; bool flag;

map <int,bool> vis;
map <int,int> calc;

int main(){
    #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    #endif

    scanf("%lld%lld%lld",&p,&b,&n);
    t=sqrt(p);

    ll tmp=n; lor(i,1,t) {vis[tmp]=true; calc[tmp]=i-1; (tmp*=b)%=p;}

    ans=-1;
    ll base=1; lor(i,1,t) (base*=b)%=p; tmp=base;
    lor(i,1,t+1){
        if(vis[tmp]) {ans=i*t-calc[tmp]; break;}
        (tmp*=base)%=p;
    }

    if(ans==-1) printf("no solutionn");
    else printf("%lldn",ans);

    return 0;
}

一遍AC不要太爽=￣ω￣=

1.4 例题

P3846 [TJOI2007]可爱的质数

P2485 [SDOI2011]计算器

2.1 exBSGS

解决了BSGS的互质情况，尝试解决更加广泛的情况:(gcd(a,p)=数字)手动滑稽(/▽＼)

大体思路是:把方程调整到BSGS能解的方程

一个比较显然的结论：设(d=gcd(a,b,p))，如果有(aequiv b (mod p))，就有(frac{a}{d}equiv frac{b}{d} (mod frac{p}{d}))

口胡证明：(aequiv b (mod p))可以转化为(a=ktimes p + b)；(frac{a}{d}=ktimes frac{p}{d} + frac{b}{d})，代回去(frac{a}{d}equiv frac{b}{d} (mod frac{p}{d}))

对于(a^xequiv b (mod p)),取(d=gcd(a,p))

（1） (dnmid b)，则根据裴蜀定理，若(b=1)，则答案为(x=0)，否则无解。

证明：

由裴蜀定理知，(atimes x + p times y =k times gcd(a,p)=ktimes d)

(dnmid bRightarrow (ktimes d) nmid b)

(atimes x +ptimes y not = b)

(anot = b (mod p))

(2) 否则方程可以进一步转移

整理如下：

如此递归下去，直至(gcd(a,b)=1)，然用BSGS解决，代回即可( •̀ ω •́ )✧

!!TIPS:我犯过的错误

一、 事实上没有必要每一次都判一遍(dnmid b)，因为特解只有一种可能(b=1,x=0)，只需要提前判一遍，只后倘若出现(dnmid b)，就是无解情况。

二、 注意好取模，每一次先算出来(p)，只后用正确的模数及时取模

三、 各种小细节很烦琐，构清楚再动手

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lor(a,b,c) for(register int a=b;a<=c;++a)
#define ror(a,b,c) for(register int a=c;a>=b;--a)

ll a,b,c,d,p,t,ans,base,tmp,cnt;

map <int,int> vis;

inline ll gcd(ll,ll);
inline ll qsm(ll,ll,ll);

int main(){
   #ifndef ONLINE_JUDGE
   freopen("test.in","r",stdin);
   freopen("test.out","w",stdout);
   #endif

   while(scanf("%lld%lld%lld",&a,&p,&b),a||p||b){
    d=1; cnt=0;
    bool flag=false;
    while((c=gcd(a,p))!=1){
        if(b%c) {printf("No Solutionn"); flag=true; break;}
        cnt++; b/=c; p/=c;
        d=d*(a/c)%p;
        if(d==b) {printf("%lldn",cnt); flag=true; break;}
    }
    if(flag) continue;
    t=ceil(sqrt(p));
    tmp=b%p; vis.clear();
    lor(i,1,t) {(tmp*=a)%=p;vis[tmp]=i;}
    base=qsm(a,t,p); tmp=d; ans=-1;
    lor(i,1,t) {(tmp*=base)%=p; if(vis[tmp]) {ans=i*t-vis[tmp]+cnt; break;}}
    tmp=1;
    lor(i,1,cnt) {(tmp*=a)%=p; if(tmp==(b%p)) {ans=i; break;}}
    if(ans==-1) printf("No Solutionn");
    else printf("%dn",ans);
   }

   return 0;
}

inline ll gcd(ll a,ll b){
   return b?gcd(b,a%b):a;   
}

inline ll qsm(ll a,ll k,ll mod){
   ll ans=1,base=a;
   while(k){
    if(k&1) (ans*=base)%=mod;
    (base*=base)%=mod;
    k>>=1;
   }
   return ans;
}

常数大，需要吸氧(～o￣3￣)～

2.2 例题

P4195 【模板】exBSGS/Spoj3105 Mod