BSGS&EXBSGS 大手拉小手,大步小步走

2018/07/03 23:43
阅读数 36

大步小步走算法处理这样的问题:

A^x = B (mod C)

求满足条件的最小的x(可能无解)

其中,A/B/C都可以是很大的数(long long以内)

 

先分类考虑一下:

当(A,C)==1 即A、C互质的时候,

叫他BSGS:

A一定存在mod C意义下的逆元,所以,A^k也存在。

注意到,A^(fai(c)) = 1 (mod c)  ......................(fai(c)表示c的欧拉函数值)

所以,A^(fai(c)+1) = A (mod C) 就重新回去了。

所以,最小的x值,如果有解,必然小于等于fai(c)

枚举显然是不可靠的。

这样考虑:将对数值分解:x=x1+x2;

将A^(0~sqrt(fai(c)) mod C 算出来,加入到一个hash表中,

这样,A^x=A^(x1+x2) 让 x1 取成:0*sqrt(fai(c) ,1*(sqrt(fai(c)) ,2*(sqrt(fai(c)) ... fai(c)

A^(p*sqrt(fai(c))+x2) = B mod C

因为,A^k都存在逆元,所以可以直接把A^(sqrt(fai(c))逆元预处理出来,再在每次循环p的时候,把A^(p*sqrt(fai(c))除过去;

即:A^x2 = B*ni mod C

对于这个B*ni(取模后),只需要在之前处理的hash表中查一下有没有出现就可以、

出现了就对应一个x2,对于x ,就是p*sqrt(fai(c))+x2

否则继续循环p

为了保证这个x是最小的x,

我们在建hash表的时候,是x的值从小到大建,如果这个值之前没有出现,就插入,否则不进行操作(相当于用小的x覆盖大的)

②我们分块的时候,从小到大枚举p,所以找到的第一个就是答案。

如果一直没有找到,就返回无解。

复杂度:O(sqrt(c)) (哈希表用邻接表挂链实现,不用map的log复杂度)

BSGS代码:poj2417(这个保证了模数是质数(直接用的费马),但是其实不一定是)

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=46349;
const int mod=100003;
ll p,A,B;
ll ni[N];
struct node{
    int nxt[mod],val[mod],id[mod],cnt;
    int hd[mod];
    void init(){
        memset(nxt,0,sizeof nxt),memset(val,0,sizeof val);cnt=0;
        memset(hd,0,sizeof hd);memset(id,0,sizeof id);
    }
    void insert(ll x,int d){
        int st=x%mod;
        for(int i=hd[st];i;i=nxt[i]){
            if(val[i]==x) return;
        }
        val[++cnt]=x;nxt[cnt]=hd[st];id[cnt]=d;hd[st]=cnt;
    }
    int find(ll x){
        int st=x%mod;
        for(int i=hd[st];i;i=nxt[i]){
            if(val[i]==x) return id[i];
        }
        return -233;
    }
}ha;
map<ll,int>mp;
ll qm(ll a,ll b){
    ll ret=1,base=a;
    while(b){
        if(b&1) ret=(ret*base)%p;
        base=(base*base)%p;
        b>>=1;
    }
    return ret;
}
ll BSGS(){
    ll up=(ll)floor(sqrt(1.0*p-1))+1;
    cout<<up<<endl;
    ni[0]=1;
    for(int i=1;i<=up;i++){
        ni[i]=qm(qm(A,i*up),p-2);
    }
    for(int i=0;i<up;i++){
        ll t=qm(A,i);
        ha.insert(t,i);
    }
    for(int i=0;i<=up;i++){
        if(i*up>p-1) break;
        ll ri=B*ni[i]%p;
        ll ret=ha.find(ri);
        if(ret>=0) return i*up+ret;
    }
    return -233;
}
int main()
{
    while(scanf("%lld",&p)!=EOF){
        scanf("%lld%lld",&A,&B);
        ha.init();
        ll ret=BSGS();
        if(ret==-233){
            puts("no solution");
        }
        else{
            printf("%lld\n",ret);
        }
    }
    return 0;
}
BSGS

 

 

EXBSGS:

如果(A,C)!=1怎么办?

转化成互质的!!

设g=gcd(A,C)
A^x = B mod C

如果B不能被g整除,就break掉;(后面已经没意义了)

否则同除以g A^(x-1) * A/g = B/g mod C/g

这个是等价的变形。

注意到,A/g C/g 是互质的。

设g=gcd(A, C/g)

循环处理。。。。。

直到g == 1结束。

设进行了num次,现在得到的等式是:

A^(x-num) * A/πg = B/πg mod C/πg

现在,A和C/πg是互质的了。

A/πg也和C/πg互质,所以直接转化成逆元,乘过去。

形式是这样的:

A^x = NB mod C

其中(A,C)=1可以用BSGS了。

注意:这里求出来的是x>=num 的最小解

我们还要暴力枚举一发x = 0~num

直接通过原式子验证。

因为num一定是log级别的,所以不费事。

 

EXBSGS代码:poj3243

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=31630;//sqrt fai()
const int mod=100003;
ll C,A,B;
ll ni[N];
struct node{
    int nxt[mod],val[mod],id[mod],cnt;
    int hd[mod];
    void init(){
        memset(nxt,0,sizeof nxt),memset(val,0,sizeof val),memset(id,0,sizeof id);
        memset(hd,0,sizeof hd),cnt=0;
    }
    void insert(ll x,int d){
        int st=x%mod;
        for(int i=hd[st];i;i=nxt[i]){
            if(val[i]==x) return;
        }
        val[++cnt]=x,nxt[cnt]=hd[st],id[cnt]=d,hd[st]=cnt;
    }
    int find(ll x){
        int st=x%mod;
        for(int i=hd[st];i;i=nxt[i]){
            if(val[i]==x) return id[i];
        }    
        return -233;
    }
}ha;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1,y=0;return;
    }
    exgcd(b,a%b,y,x);
    y-=(a/b)*x;
}
ll qm(ll a,ll b,ll p){
    ll ret=1,base=a;
    while(b){
        if(b&1) ret=(base*ret)%p;
        base=(base*base)%p;
        b>>=1;
    }
    return ret;
}
int gcd(int a,int b){
    return (b==0)?a:gcd(b,a%b);
}
int BSGS(ll a,ll b,ll c){
    int up=(int)floor(sqrt(1.0*c-1))+1;
    ll ni=0,yy=0;
    exgcd(qm(a,up,c),c,ni,yy);
    ni=(ni%c+c)%c;//warning!!! 必须变成正数 
    ll kk=1;
    for(int i=0;i<=up-1;i++){
        ha.insert(kk,i);
        kk=(kk*a)%c;
    }
    ll bb=b;
    for(int i=0;i<=up;i++){
        int kk=ha.find(bb);
        if(kk>=0) return i*up+kk;
        bb=(bb*ni)%c;//不断找逆元 递推就可以 
    }
    return -233;
}
int EXBSGS(){
    int num=0;
    int yC=C;
    int yB=B;
    int yA=A;
    ll ji=1;
    int ret=-233;
     bool flag=false;    
    while(1){
        int g=gcd(A,C);
        if(g==1) break;
        if(B%g) {
            flag=true;break;
        }
        B/=g,C/=g,ji=(ji*A/g)%C;
        num++;
    }
    for(int i=0;i<=num;i++){
        ll kk=qm(yA,i,yC);
        if(kk%yC==yB) return i;
    }
    if(!flag){
        ll ni,yy;
        exgcd(ji,C,ni,yy);
        ni=(ni%C+C)%C;//warning!!! 必须变成正数 
        ll NB=(B*ni)%C;
        ret=BSGS(A,NB,C);
    }
    if(ret>=0) return ret+num;
    else return -233;
}
int main(){
    while(1){
        scanf("%lld%lld%lld",&A,&C,&B);
        if(A==0&&B==0&&C==0) break;
        ha.init();
        B%=C;
        int ret=EXBSGS();
        if(ret>=0){
            printf("%d\n",ret);
        }
        else{
            puts("No Solution");
        }
    }
    return 0;
}
EXBSGS

 

我的易错点:

①BSGS和EXBSGS中,总是忘了对B或者NB取模,就爆long long 了。(日常模一模)

②C不一定是质数,所以用exgcd求逆元(欧拉定理亲测也行,只要你不嫌sqrt麻烦)

③分块求每一块大小的时候,up=floor(sqrt(C))+1注意一定要加一,否则floor就卡下去了。对于C是质数,就可能不能取到C-1

比如:73^x = 71 mod 139 (139是质数)的解是:136

如果不加1,up=11 那么,最多能分块到:121+11=132 就输出无解了。

④用exgcd求逆元的时候,必须把求出来的逆元:ni=(ni%C+C)%C转化为正数!!!

 

展开阅读全文
fai
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部