给定 \(y,z,p\),求最小的正整数 \(x\) 满足 \(y^x\equiv z\bmod p\),保证 \(p\) 是质数。
\(\texttt{Data Range:}2\leq y,z<p<^{31}\)
BSGS 裸题。
这题其实我一年前就做过了,但是现在发现差点背不得 BSGS 了,所以重新写了一遍。
背 BSGS 其实只要掌握原理就好了。
首先考虑分块。令 \(x=am-b,m=\sqrt{p}\),那么就有
\[y^{am}\equiv zy^b\pmod p
\]
注意到由于 \(b\) 只有 \(\sqrt{b}\) 种取值方法,所以可以将所有可能的 \(zy^b\) 拿个哈希表存下来。
然后枚举 \(a\),暴力查 \(y^{am}\) 在哈希表里有没有对应的值就好了。
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=2e5+51;
unordered_map<ll,ll>hsh;
ll x,y,MOD,res;
inline ll read()
{
register ll num=0,neg=1;
register char ch=getchar();
while(!isdigit(ch)&&ch!='-')
{
ch=getchar();
}
if(ch=='-')
{
neg=-1;
ch=getchar();
}
while(isdigit(ch))
{
num=(num<<3)+(num<<1)+(ch-'0');
ch=getchar();
}
return num*neg;
}
inline ll qpow(ll base,ll exponent)
{
ll res=1;
while(exponent)
{
if(exponent&1)
{
res=(li)res*base%MOD;
}
base=(li)base*base%MOD,exponent>>=1;
}
return res;
}
inline ll find(ll x)
{
return hsh.find(x)==hsh.end()?-1:hsh[x];
}
inline ll BSGS(ll base,ll res)
{
ll blk=sqrt(MOD)+1,v=(res%=MOD),x;
hsh.clear(),base%=MOD;
for(register int i=0;i<=blk;i++)
{
hsh[v]=i,v=(li)v*base%MOD;
}
base=qpow(base,blk),v=1;
if(!base)
{
return !res?1:-1;
}
for(register int i=0;i<=blk;i++)
{
x=find(v),v=(li)v*base%MOD;
if(x>=0&&i*blk-x>=0)
{
return i*blk-x;
}
}
return -1;
}
int main()
{
MOD=read(),x=read(),y=read(),res=BSGS(x,y);
res==-1?puts("no solution"):printf("%d\n",res);
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章