题解 P4454 【[CQOI2018]破解D-H协议】

P4454 [CQOI2018]破解D-H协议

题目本质是求解高次同余方程，复杂度允许，使用 BSGS 算法。

模板 P3846

我的 BSGS 算法学习笔记

题目中也提到，双方获得的是相同的 K ，所以只要对其中一组方程求解，然后快速幂输出答案即可。

注意每次跑 BSGS 要清空。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

inline int qpow(int x,int y,int p)
{
    int res=1;
    while(y)
    {
        if(y&1) res=1ll*res*x%p;
        y>>=1; x=1ll*x*x%p;
    }
    return res;
}

map <int,int> _hash;
inline int BSGS(int a,int b,int p)
{
    b%=p; _hash.clear();
    int t=ceil(sqrt(p)),val=1;
    for(int i=0;i<t;i++)
    {
        _hash[1ll*b*val%p]=i;
        val=1ll*val*a%p;
    }
    a=val; val=1;

    if(!a) return !b? 1:-1;
    for(int i=0,j;i<=t;i++)
    {
        j=_hash.find(val) == _hash.end()? -1:_hash[val];
        if(~j && i*t-j >= 0) return i*t-j;
        val=1ll*val*a%p;
    }
    return -1;
}

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    int g,p,n,A,B,a;
    scanf("%d%d%d",&g,&p,&n);
    while(n--)
    {
        scanf("%d%d",&A,&B);
        a=BSGS(g,A,p);
        printf("%d\n",qpow(B,a,p));
    }
//  fclose(stdin); fclose(stdout);
    return 0;
}

一些 BSGS 的题：

• P2485 [SDOI2011]计算器
• P3306 [SDOI2013] 随机数生成器
• P4884 多少个1？
• P4861 按钮 题解

\text{Thank you for your reading !}