bsgs整理

bsgs问题或 poj2417：
概述
代码
exbsgs
鸣谢 $gzy gzy gzy$

bsgs问题或 poj2417：

给定质数$p$，给定$a$,$b$,$(a,p)=1$

求出最小的整数x，使得$a^{x}≡b(mod p)$

概述

由费马小定理可以知道

$a^{x+p-1}≡a^{x}≡b(mod p)$

所以如果有解那$[0,p-1]$区间内一定会出现解

让$m=sqrt(p)$

$x$可以表示为$m*i-j$

那$m,i,j$都是在根号规模的

$a^{m*i-j}≡b(mod p)$

$\frac{a^{m*i}}{a^{j}}≡b(mod p)$

$a^{m*i}≡b*a^{j}(mod p)$

右边$hash$表（一般都用stl的map）存在所有的j取值

左边暴力枚举i(因为是-j，所以从1枚举，要不然就成负数了，找出来的就不一定是最小解)

如果$a^{m*i}$在hash表中存在，那就有解，也是最小解，结束吧

如果根号范围内还没有解，那就真的没解

算法思想：分块

算法缺陷：p是质数

算法复杂度$\sqrt{n}$

$map$常数也许很高

代码

#include <iostream>

#include <cmath>

#include <map>

#include <cstdio>

#define ll long long

using namespace std;

ll a,b,p;

map<ll,ll> hasH;

int main() {

	while(scanf("%lld%lld%lld",&p,&a,&b)!=EOF) {

		ll m=floor(sqrt(p));

		hasH.clear();

		ll tmp=1;

		hasH[b]=1;

		for(ll i=1;i<=m;++i) tmp=tmp*a%p,hasH[tmp*b%p]=i+1;

		ll xx=tmp,i=1,ans=-1;

		for(;i<=m;++i) {

			if(hasH[xx]) {ans=m*i%p-(hasH[xx]-1);break;}

			xx=xx*tmp%p;

		}

		if(ans==-1) puts("no solution");

		else printf("%d\n",ans);

	}

	return 0;

}

exbsgs

咕咕咕咕

gzy

bsgs整理

bsgs问题 或 poj2417：

概述

代码

exbsgs

鸣谢 \(gzy gzy gzy\)

bsgs问题或 poj2417：