【BZOJ 2480】[SPOJ 3105] Mod

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2480
数据生成器:http://paste.ubuntu.com/23021720/

同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;
	int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T;
	
	inline void init(){memset(head,0,sizeof(head)); T=0;}
	
	inline void insert(int v, int d) {
		nxt[++T] = head[v%MOD];
		val[T] = v; data[T] = d; 
		head[v%MOD] = T;
	}
	
	inline int query(int v){
		for (int i=head[v%MOD];i;i=nxt[i]) 
			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】同余方程

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2995
数据生成器:http://paste.ubuntu.com/23021720/

拓展BSGS板题

#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;
	int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T;
	
	inline void init(){memset(head,0,sizeof(head)); T=0;}
	
	inline void insert(int v, int d) {
		nxt[++T] = head[v%MOD];
		val[T] = v; data[T] = d; 
		head[v%MOD] = T;
	}
	
	inline int query(int v){
		for (int i=head[v%MOD];i;i=nxt[i]) 
			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;
} 

这里有一份不带log的算法:http://paste.ubuntu.com/23021654/
不过我看不懂QAQ,就不管啦! *★,°*:.☆( ̄▽ ̄)/$:*.°★* 。

——— 2016.8.12更新 ———
不带log的版本,rank 3!

#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;
    int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T;
     
    inline void init(){memset(head,0,sizeof(head)); T=0;}
     
    inline void insert(int v, int d) {
        nxt[++T] = head[v%MOD];
        val[T] = v; data[T] = d; 
        head[v%MOD] = T;
    }
     
    inline int query(int v){
        for (int i=head[v%MOD];i;i=nxt[i]) 
            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 —–
之前的程序仍然有bug,会被3 9 3这种数据卡掉
非常感谢wyh神犇提供的数据 _(:зゝ∠)_
这是改正之后的程序:

#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;
    int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T;
     
    inline void init(){memset(head,0,sizeof(head)); T=0;}
     
    inline void insert(int v, int d) {
        nxt[++T] = head[v%MOD];
        val[T] = v; data[T] = d; 
        head[v%MOD] = T;
    }
     
    inline int query(int v){
        for (int i=head[v%MOD];i;i=nxt[i]) 
            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] 计算器

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2242
数据生成器:http://paste.ubuntu.com/22875643/
数据传送门:http://pan.baidu.com/s/1dE71QHr

这个题,做了一个下午+一个晚上,最后才发现是把”cannot”中间多加了一个‘a’
MD,老子好想杀人! (╯‵□′)╯︵┻━┻

题目本身很简单,就是快速幂+拓展欧几里得+BSGS
但网上的程序,多少有问题,反正我能搜出来的,我都可以叉掉
我这份代码问题应该比较少吧:

#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;
	int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T;
	
	inline void init(){
		T = 0;
		memset(head,0,sizeof(head));
	}
	
	inline void insert(int w, int d){
		nxt[++T] = head[w%MOD];
		val[T] = w; data[T] = d;
		head[w%MOD] = T;
	}	
	
	inline int find(int w){
		for (int i=head[w%MOD];i;i=nxt[i])
			if (val[i] == w) return data[i];
		return -1;
	}
};

inline int read(){
	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(){
	int T=read(),ty=read(); while (T--) {
		int a=read(), b=read(), c=read();
		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

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3239
离线版题目:http://paste.ubuntu.com/19379662/

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;
	int T,nxt[N/2],v1[N/2],head[N],v2[N/2];
	
	inline void insert(int w, int num){
		v1[++T] = w; v2[T] = num;
		nxt[T] = head[w%MOD]; head[w%MOD] = T;
	}
	
	inline void init(){
		memset(head,0,sizeof(head));
		T = 0;
	}
	
	inline int query(int w){
		int ret = INF;
		for (int i=head[w%MOD];i;i=nxt[i])
			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;
}