bsgs_and_exbsgs

## 【BZOJ 2480】[SPOJ 3105] Mod

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;

const double EPS = 1e-3;
const int MAXN = 100000;

int a,b,c;

namespace Hash{
const int MOD = 99971;

inline void insert(int v, int d) {
val[T] = v; data[T] = d;
}

inline int query(int v){
if (val[i] == v) return data[i];
return -1;
}
};

inline int pow(int w, int t, int p){
int ret = 1;
while (t) {
if (t & 1) ret  = (LL)ret*w % p;
w = (LL)w*w % p; t >>= 1;
}
return ret;
}

int GCD(int a, int b) {return b?GCD(b,a%b):a;}

void EX_GCD(int a, int b, LL &x, LL &y) {
if (!b) x = 1, y = 0;
else EX_GCD(b,a%b,y,x), y -= a/b*x;
}

inline int EX_GCD(int a, int b, int pur){
LL ret,tmp; EX_GCD(a,b,ret,tmp);
return (ret*pur%b+b) % b;
}

inline void BSGS(){
int cnt = 0,tmp,sta=1,sld[32],A=a,B=b,C=c; a %= c; b %= c;
while ((tmp=GCD(a,c)) > 1)
if (b % tmp) {printf("No Solution\n"); return;}
else sld[++cnt] = a / tmp, b /= tmp, c /= tmp;
for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;}
for (int i=1;i<=cnt;i++) sta = (LL)sta*sld[i]%c;

Hash::init();
int lim = int(ceil(sqrt(c)) + EPS);
for (int i=0,w=1;i<=lim;i++,w=(LL)w*a%c) {
if ((LL)w*sta%c == b) {printf("%d\n",i+cnt); return;}
else Hash::insert((LL)w*sta%c,i);
}

for (int i=1,w=pow(a,lim,c),ori=w;i<=lim;i++,w=(LL)w*ori%c) {
tmp = Hash::query(EX_GCD(w,c,b)); //if (i == 1) cout<<w<<endl;
if (~tmp) {printf("%d\n",i*lim+tmp+cnt); return;}
}
printf("No Solution\n");
}

int main(){
while (~scanf("%d%d%d",&a,&c,&b) && a) BSGS();
return 0;
}


## 【BZOJ 2995】同余方程

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;

const double EPS = 1e-3;
const int MAXN = 100000;

int a,b,c;

namespace Hash{
const int MOD = 99971;

inline void insert(int v, int d) {
val[T] = v; data[T] = d;
}

inline int query(int v){
if (val[i] == v) return data[i];
return -1;
}
};

inline int pow(int w, int t, int p){
int ret = 1;
while (t) {
if (t & 1) ret  = (LL)ret*w % p;
w = (LL)w*w % p; t >>= 1;
}
return ret;
}

int GCD(int a, int b) {return b?GCD(b,a%b):a;}

void EX_GCD(int a, int b, LL &x, LL &y) {
if (!b) x = 1, y = 0;
else EX_GCD(b,a%b,y,x), y -= a/b*x;
}

inline int EX_GCD(int a, int b, int pur){
LL ret,tmp; EX_GCD(a,b,ret,tmp);
return (ret*pur%b+b) % b;
}

inline void BSGS(){
int cnt = 0,tmp,sta=1,sld[32],A=a,B=b,C=c; a %= c; b %= c;
while ((tmp=GCD(a,c)) > 1)
if (b % tmp) {printf("No Solution\n"); return;}
else sld[++cnt] = a / tmp, b /= tmp, c /= tmp;
for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;}
for (int i=1;i<=cnt;i++) sta = (LL)sta*sld[i]%c;

Hash::init();
int lim = int(ceil(sqrt(c)) + EPS);
for (int i=0,w=1;i<=lim;i++,w=(LL)w*a%c) {
if ((LL)w*sta%c == b) {printf("%d\n",i+cnt); return;}
else Hash::insert((LL)w*sta%c,i);
}

for (int i=1,w=pow(a,lim,c),ori=w;i<=lim;i++,w=(LL)w*ori%c) {
tmp = Hash::query(EX_GCD(w,c,b)); //if (i == 1) cout<<w<<endl;
if (~tmp) {printf("%d\n",i*lim+tmp+cnt); return;}
}
printf("No Solution\n");
}

int main(){
while (~scanf("%d%d%d",&a,&c,&b) && a) BSGS();
return 0;
}


——— 2016.8.12更新 ———

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;

const double EPS = 1e-3;
const int MAXN = 100000;

int a,b,c;

namespace Hash{
const int MOD = 99971;

inline void insert(int v, int d) {
val[T] = v; data[T] = d;
}

inline int query(int v){
if (val[i] == v) return data[i];
return -1;
}
};

inline int pow(int w, int t, int p){
int ret = 1;
while (t) {
if (t & 1) ret  = (LL)ret*w % p;
w = (LL)w*w % p; t >>= 1;
}
return ret;
}

int GCD(int a, int b) {return b?GCD(b,a%b):a;}

void EX_GCD(int a, int b, LL &x, LL &y) {
if (!b) x = 1, y = 0;
else EX_GCD(b,a%b,y,x), y -= a/b*x;
}

inline int EX_GCD(int a, int b, int pur){
LL ret,tmp; EX_GCD(a,b,ret,tmp);
return (ret*pur%b+b) % b;
}

inline void BSGS(){
int cnt = 0,tmp,sta=1,sld[32],A=a,B=b,C=c; a %= c; b %= c;
while ((tmp=GCD(a,c)) > 1)
if (b % tmp) {printf("No Solution\n"); return;}
else sld[++cnt] = a / tmp, b /= tmp, c /= tmp;
for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;}
for (int i=1;i<=cnt;i++) sta = (LL)sta*sld[i]%c;

Hash::init();
int lim = int(ceil(sqrt(c)) + EPS);
for (int i=0,w=1;i<=lim;i++,w=(LL)w*a%c) {
if ((LL)w*sta%c == b) {printf("%d\n",i+cnt); return;}
else Hash::insert((LL)w*sta%c,i);
}

int w_ori = pow(a,lim,c), rev_ori = EX_GCD(w_ori,c,1);
for (int i=1,rev=rev_ori;i<=lim;i++,rev=(LL)rev*rev_ori%c) {
tmp = Hash::query((LL)rev*b%c);
if (~tmp) {printf("%d\n",i*lim+tmp+cnt); return;}
}
printf("No Solution\n");
}

int main(){
while (~scanf("%d%d%d",&a,&c,&b) && a) BSGS();
return 0;
}


—– UPD 2016.9.19 —–

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const double EPS = 1e-3;
const int MAXN = 100000;

int a,b,c;

namespace Hash{
const int MOD = 99971;

inline void insert(int v, int d) {
val[T] = v; data[T] = d;
}

inline int query(int v){
if (val[i] == v) return data[i];
return -1;
}
};

inline int pow(int w, int t, int p){
int ret = 1;
while (t) {
if (t & 1) ret  = (LL)ret*w % p;
w = (LL)w*w % p; t >>= 1;
}
return ret;
}

int GCD(int a, int b) {return b?GCD(b,a%b):a;}

void EX_GCD(int a, int b, LL &x, LL &y) {
if (!b) x = 1, y = 0;
else EX_GCD(b,a%b,y,x), y -= a/b*x;
}

inline int EX_GCD(int a, int b, int pur){
LL ret,tmp; EX_GCD(a,b,ret,tmp);
return (ret*pur%b+b) % b;
}

inline void SPJ(int A, int B, int C, int cnt){
for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;}
printf("No Solution\n");
}

inline void BSGS(){
int cnt = 0,tmp,sta=1,sld[32],A=a,B=b,C=c; a %= c; b %= c;
while ((tmp=GCD(a,c)) > 1)
if (b % tmp) {SPJ(A,B,C,cnt);return;}
else sld[++cnt] = a / tmp, b /= tmp, c /= tmp;
for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;}
for (int i=1;i<=cnt;i++) sta = (LL)sta*sld[i]%c;

Hash::init();
int lim = int(ceil(sqrt(c)) + EPS);
for (int i=0,w=1;i<=lim;i++,w=(LL)w*a%c) {
if ((LL)w*sta%c == b) {printf("%d\n",i+cnt); return;}
else Hash::insert((LL)w*sta%c,i);
}

for (int i=1,w=pow(a,lim,c),ori=w;i<=lim;i++,w=(LL)w*ori%c) {
tmp = Hash::query(EX_GCD(w,c,b));
if (~tmp) {printf("%d\n",i*lim+tmp+cnt); return;}
}
printf("No Solution\n");
}

int main(){
while (~scanf("%d%d%d",&a,&c,&b) && a) BSGS();
return 0;
}


## 【BZOJ 2242】[SDOI2011] 计算器

MD，老子好想杀人！ (╯‵□′)╯︵┻━┻

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 100000;
const double EPS = 1e-5;

namespace Hash{
const int MOD = 99971;

inline void init(){
T = 0;
}

inline void insert(int w, int d){
val[T] = w; data[T] = d;
}

inline int find(int w){
if (val[i] == w) return data[i];
return -1;
}
};

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline int quick_pow(int a,int b,int c){
int ret = 1; while (b) {
if (b & 1) ret = ((LL)ret * a) % c;
a = (LL)a*a%c; b >>= 1;
} return ret;
}

int GCD(int a, int b){return b?GCD(b,a%b):a;}

void EX_GCD(int a, int b, int &x, int &y){
if (!b) x=1, y=0;
else EX_GCD(b,a%b,y,x), y-=a/b*x;
}

inline int EX_GCD(int a, int b, int c) {
int ret,tmp,gcd=GCD(a,b);
if (c%gcd) return -1;
else {
EX_GCD(a/gcd,b/gcd,ret,tmp);
ret = (((LL)c/gcd*ret) % b + b) % b;
return ret;
}
}

inline void solve(int a, int b, int c) {
int ret = EX_GCD(a,c,b);
if (~ret) printf("%d\n",ret);
else printf("Orz, I cannot find x!\n");
}

inline void BSGS(int a, int b, int c) {
Hash::init(); a %= c; b %= c;
if (!a && b > 1) {printf("Orz, I cannot find x!\n"); return;}

int lim = int(ceil(sqrt(c))+EPS);
for (int i=0,w=1;i<=lim;i++) {
if (w == b) {printf("%d\n",i); return;}
Hash::insert(w,i);
w = ((LL)w*a) % c;
}

int w_ori = quick_pow(a,lim,c), rev_ori = quick_pow(w_ori,c-2,c);
for (int i=1,w=w_ori,rev=rev_ori;i<=lim;i++) {
int tmp = Hash::find(((LL)rev*b) % c);
if (tmp > -1) {printf("%d\n",i*lim+tmp); return;}
w = ((LL)w*w_ori) % c;
rev = ((LL)rev*rev_ori) % c;
}
printf("Orz, I cannot find x!\n");
}

int main(){
if (ty == 1) printf("%d\n",quick_pow(a,b,c));
else if (ty == 2) solve(a,b,c);
else BSGS(a,b,c);
}
return 0;
}


## 【BZOJ 3239】Discrete Logging

BSGS 的板题，然而把MAXINT记成2e10去了，调试了两个小时QAQ
BSGS 见算法总结，这么晚了，今天先扔一份代码就跑了吧QAQ

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 9999971;

int p,a,b;

namespace Hash{
const int N = 10000000;
const int MOD = 9999971;
const int INF = 2000000000;

inline void insert(int w, int num){
v1[++T] = w; v2[T] = num;
}

inline void init(){
T = 0;
}

inline int query(int w){
int ret = INF;
if (v1[i] == w) ret = min(ret, v2[i]);
if (ret != INF) return ret;
else return -1;
}
};

inline int quick_pow(int w, int t){
int ret = 1;
while (t) {
if (t & 1) ret = ((LL)ret*w) % p;
w = (LL)w*w % p; t >>= 1;
}
return ret;
}

inline void BSGS(){
Hash::init();
if (b == 1) printf("0\n");
else {
int w = a, lim = ceil(sqrt(p));
for (int i=1;i<=lim;i++) {
if (w == b) {printf("%d\n",i); return;}
Hash::insert(w,i); w = (LL)w*a%p;
}
a = w = quick_pow(a,lim);
for (int i=1;i<=lim;i++) {
int tmp = Hash::query((LL)b*quick_pow(w,p-2)%p);
if (tmp > -1) {printf("%d\n",lim*i+tmp); return;}
w = (LL)w*a%p;
}
printf("no solution\n");
}
}

int main(){
while (~scanf("%d%d%d",&p,&a,&b)) BSGS();
return 0;
}