Luogu P3846 [TJOI2007] 可爱的质数/【模板】BSGS

题意

给定 \(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);

}

巴特西

Luogu P3846 [TJOI2007] 可爱的质数/【模板】BSGS

题意

题解

代码

最新文章

热门文章