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;
}