题目

题目链接：https://www.luogu.com.cn/problem/P3846
给出\(a,b,p\)，保证\(p\)是质数，求一个最小的\(k\)满足\(a^k\equiv n(\rm \mod\ p)\)

思路：

\(BSGS\)模板题。果然我菜到只会敲模板了吗。
设\(t=\sqrt{p},k=i\times t-j\)，那么移项得\((a^t)^i \equiv b\times a^j\)，其中\(i,j\leq t\)。
那么我们可以把\(b\times a^j(j\in [0,t])\)插入一个\(hash\)表内，然后再枚举\(i\)求出\((a^t)^i\)，如果这个值在\(hash\)表内有出现，那么答案就是\(i\times t-hash[]\)。
时间复杂度\(O(sqrt{p})\)。由于\(hash\)表我使用了\(map\)，实际上还要多一个\(log\)。

代码

#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

int a,b,p,t;
map<int,int> hash;

int power(ll x,ll k,int MOD)
{
    ll ans=1;
    for (;k;k>>=1,x=x*x%MOD)
        if (k&1) ans=ans*x%MOD;
    return (int)ans;
}

int main()
{
    scanf("%d%d%d",&p,&a,&b);
    t=sqrt(p)+1;
    for (int i=0;i<=t;i++)
        hash[1LL*b*power(a,i,p)%p]=i;
    a=power(a,t,p);
    for (int i=1;i<=t;i++)
    {
        int val=power(a,i,p);
        if (hash[val])
            return !printf("%lld",(1LL*(i*t-hash[val])%p+p)%p);
    }
    printf("no solution");
    return 0;
}

【洛谷P3846】可爱的质数

原文：https://www.cnblogs.com/stoorz/p/12235584.html