【洛谷P3846】【TJOI2007】—可爱的质数（BSGS模板）

传送门

$BSGS$（又名北上广深算法）用于求解$a^x equiv b(mod p)（pin prime）$

$BSGS$其实就是用类似分块的思想优化暴力枚举

考虑在模意义下
令$k=lfloor sqrt p floor+1$
那么$x=qk-l$
方程为 $a^{qk-l}equiv b(mod p)$

移项后 $a^{qk} equiv b*a^l (mod p)$

考虑到$l,k$的取值都最多只有$O(sqrt p)$种

我们先枚举$iin(0,l)$，求出所有$b*a^i$的取值

然后再枚举所有可能的$q$,$iin(1,k)$ ,求出所有的$a^{ik}$看存不存在这个答案

第一个枚举到的就是答案了

#include<bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;
inline int read(){
	char ch=getchar();
	int res=0;
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
	return res;
}
#define int long long
tr1::unordered_map<int,int> mp;
int n,k,mod;
inline int ksm(int a,int b,int res=1){
	for(;b;b>>=1,a=a*a%mod){
		if(b&1)res=res*a%mod;
	}
	return res;
}
signed main(){
	mod=read(),k=read(),n=read();
	int res=1;
	int M=sqrt(mod)+1;
	for(int i=0;i<=M;i++){
		mp[n*res%mod]=i;
		res=res*k%mod;
	}
	int ans=-1;
	for(int i=1;i<=M;i++){
		int tmp=ksm(k,i*M);
		if(mp[tmp]){cout<<i*M-mp[tmp]<<'
';return 0;};
	}
	cout<<"no solution";
}