BSGS学习笔记

用于求$A^{x} \equiv B \pmod{C}$ 高次方程的最小正整数解x，其中C为素数

引理1：$a^{i\mod\varphi(p) } \equiv a^{i} $ (mod p) p为素数，即$a^i$在模p的意义下会出现循环节(注:$\varphi(p)$不是最小循环节)

证明：

因为$ a^{p-1} \equiv 1 $ (mod p) (费马小定理) ,则 $a^{k*(p-1)} \equiv 1$ (mod p)

所以$ a^{2k * (p-1)} * a^{-k * (p-1)} \equiv 1 $ (mod p)

所以$ a^{2k * (p-1)} $ 为 $a^{-k * (p-1)}$ mod p意义下的逆元

$ \frac{a^{i}}{a{k * (p-1)}} \equiv a^{i} * a^{2k * (p-1)} \equiv a^{i} * 1 \equiv a^{i} $ (mod p)

即$ a^{i-k*(p-1)} \equiv a^{i} $ (mod p)

又因为$ i \bmod \varphi(p) = i-k*(p-1) $

且p为素数,$i-k*(p-1)=i-k * \varphi(p)$

则$ a^{i-k*(p-1)} \equiv a^{i\mod\varphi(p)} \equiv a^{i} $ (mod p)

证毕!

根据引理1我们可知只需要枚举至多$\varphi(C)$个数就能知道方程的解，若枚举完后发现无解，则整个方程无解

考虑构造一个m，使得$m=ceil(\sqrt{C})$ (其中ceil()为向上取整函数)

$x=k*m-q$，原方程转化为$ A^{k * m-q} \equiv B \pmod{p}$

继续得到 $ A^{k * m} \equiv B*A^{q} \pmod{p}$

BSGS流程：到了这一步，我们先考虑枚举$B*A^{q}$中的q,至多$\sqrt{C}$次，然后我们把得到的值存入一个Hash表中

接着我们开始枚举 $ A^{k * m}$ 中的m，则两次枚举出来的式子的两两组合正好可以得到所有$range \in [1,x] $(作者就是被这个地方卡了一万年QwQ)，若遇到两次枚举出来的值相等，则输出答案，退出循环。

(注:作者写这题的时候运势不好，Hash写挂了，换成了map，效果不影响)

Code:

#include<stdio.h>

#include<math.h>

#include<map>

using namespace std;

#define ll long long

#define int ll

#define HASH_MOD 76799777LL

map<int,int> hash;

ll qpow(ll A,ll B,ll C){

	if(B==0) return 1;

	if(B==1) return A;

	ll t=qpow(A,B>>1,C);

	t=t*t%C;

	if(B&1) t=t*A%C;

	return t;

}

ll BSGS(ll A,ll B,ll C){

	const int sizes=ceil(sqrt(C));

	ll base=B%C;

	hash[base]=0;

	for(int i=1;i<=sizes;i++){

		base=base*A%C;

		hash[base]=i;

	}

	base=qpow(A,sizes,C);

	ll tmp=1;

	for(ll i=1;i<=sizes;i++){

		tmp=tmp*base%C;

		if(hash[tmp])

			return ((i*sizes-hash[tmp])%C+C)%C;

	}

	return -1;

}

ll P,B,N;

signed main(){

	scanf("%lld%lld%lld",&P,&B,&N);

	if(!(B%P)){

        printf("no solution\n");

        return 0;

    }

	ll ans=BSGS(B,N,P);

	if(ans!=-1) printf("%lld",ans);

	else printf("no solution");

}

巴特西

BSGS学习笔记

最新文章

热门文章