BSGS算法

BSGS算法

前言

(BabyStepGiantStep)算法

北上广深算法，orz

算法用于解决高次同余问题，(a^xequiv b(mod c)) 满足 (gcd(a,c) = 1)

推理过程

根据费马小定理可知

如果 (a) 和 (c) 互质，满足 (a^{c-1}equiv 1(mod c)),

自此之后 (a^{c}equiv a(mod c))

这是一个循环过程，最小项维护在区间 ([0,c)) ,不能暴力求解，

有一种方法 假设 (k = ceil(sqrt(c))) ，使得 (x=k×kx-ky) ,其中 (kx epsilon [1,m],ky epsilon (0,m])

之后不断枚举 (ky) ，使用 (kx) 进行匹配就是结果。

例题

题目：洛谷 P4884

点我，快点我

题解：将 (N) 个 (1) ,逐步分开成 (10^0 + 10^1+...+10^{N-1}), 这是一个等比数列，

进一步化简得到 (10^n equiv (9*k+1) (mod m)) ,将公式代进去，输出结果即可。

#include <map>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
ll multi(ll a,ll b,ll mod){
	ll ret=0;
	while(b>0){
		if(b&1)ret=(ret+a)%mod;
		b>>=1;
		a=(a+a)%mod;
	}
	return ret;
}
ll pow(ll a,ll b,ll mod){
	ll ret=1;
	while(b>0){
		if(b&1)ret=multi(ret,a,mod);
		b>>=1;
		a=multi(a,a,mod);
	}
	return ret;
}
ll BSGS(ll a,ll b,ll m){
	ll k=ceil(sqrt(m));
	map<ll,ll>M;
	for(int i=0;i<=k;++i){
		M[b]=i;
		b=multi(b,a,m);
	}
	a=pow(a,k,m);
	ll ret=a;
	for(int i=1;i<=k;++i){
		if(M.count(ret)){
			return i*k-M[ret];
		}
		ret=multi(ret,a,m);
	}
	return 0;
}
int main(){
	ll K,m;
	cin>>K>>m;
	K=(K*9+1)%m;
	cout<<BSGS(10,K,m)<<endl;
	return 0;
}