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

· · 题解

\mathsf{Solution\text{ }For\text{ }P4454}

\large\mathcal{By\text{ }ShadderLeave}

实际上，这题本质并不难，只是需要把题目读懂......

Description

形式化描述：
给定一个质数 P ，以及模 P 意义下的一个原根 g
接下来给定若干组整数 A,B，其中 A=g^x \bmod{P},B=g^y\bmod P，求出 g^{xy}\text{ }\bmod{P} 旳值

Solution

那么这里可以看出，已知的量有 A,B,g,P。其中 g,P 不变而 A,B 有若干组，对于每一组 A,B 我们都有两个待求的量 x,y.那么第一级解法就有了：对于每一组 A,B 求出对应的 x,y，直接计算g^{xy}\text{ }\bmod{P} 旳值

但是仔细想想就会发现只用求一个就可以了，因为 A,B 已知，求出一个（这里假设求出了 x）,便可以直接拿着 B 来计算 B^x，这两种做法在模 P 意义下是等价的。

分析van了之后再把题目的形式化描述更加具体一点(有利于解题思路的清晰化)
给定一个质数 P ，以及模 P 意义下的一个原根 g
接下来给定若干组整数 A,B，其中 A=g^x \bmod{P},B=g^y\bmod P，求出同余方程 g^x\equiv A\pmod{P} 的解 x，然后计算 B^x\bmod{P} 的值

高次同余方程，模数与底数互质，用 \mathsf{BSGS} 来解出指数
关于\mathsf{BSGS} 的讲解

然后因为是多组数据
原来的同余方程是 g^x\equiv A\pmod{P} ,设 x=i\times \sqrt{P}-j
化为

\dfrac{g^{i\times\sqrt{P}}}{g^j\times A}\equiv 1\pmod{P}

为了效率，因为这里的 A 是多组数据，是变动的，而 P,g 是在一开始就给出的，所以不能再预处理分母，我们预处理分子即可

注意这里的 i,j 的范围：i\in \left( 0,ceil(\sqrt{P}) \right]，j\in \left[ 0,ceil(\sqrt{P}) \right)

总结步骤：

  1. 预处理分子部分，即 g^{i\times\sqrt{P}},其中 i\in \left( 0,ceil(\sqrt{P}) \right]
  2. 对于每一组 A,B，枚举 A\times g^j ,其中 j\in \left[ 0,ceil(\sqrt{P}) \right)，在哈希表中查询是否有对应的值存储，若有，得到 \boxed{ans=\texttt{哈希表中存储的幂指数}-j}
  3. 快速幂求出每一组中 B^{ans}\bmod{P} 的值，输出

\mathsf{Code:}

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL A,B,C;
struct Hash_table{//手写哈希真的快很多
    static const LL MOD=1999997;
    LL Hash[MOD],V[MOD],stk[MOD],top;
    //Hash_table() {memset(Hash,-1,sizeof(Hash));}
    inline void Insert(LL val,LL mi)
    {
        LL h=val%MOD;
        while(Hash[h]&&Hash[h]!=val) h++;
        Hash[h]=val;V[h]=mi;
        stk[++top]=h;
        return ;
    }
    inline LL find(LL val)
    {
        LL h=val%MOD;
        while(Hash[h]&&Hash[h]!=val) h++;
        return Hash[h]==val?V[h]:-1;
    }
}H;
inline LL fast_pow(LL b,LL k)
{
    LL s=1;
    while(k)
    {
        if(k&1) s=(s*b)%C;
        b=(b*b)%C;
        k>>=1;
    }
    return s;
}
LL N;
int main()
{
    scanf("%lld%lld",&A,&C);
    LL sqrtm=ceil(sqrt(C));
    LL ti=fast_pow(A,sqrtm);
    LL t=ti;
    for(LL i=1;i<=sqrtm;i++)//预处理分子，注意范围
    {
        H.Insert(t,i*sqrtm);
        t=t*ti%C;
    }
    scanf("%lld",&N);
    LL x,y,ans;
    for(int i=1;i<=N;i++)
    {
        scanf("%lld%lld",&x,&y);
        t=x;
        for(int j=0;j<sqrtm;j++)//枚举分母，注意范围
        {
            if((ans=H.find(t))!=-1)
            {
                ans-=j;
                printf("%lld\n",fast_pow(y,ans));
                break;
            }
            t=t*A%C;
        }
    }
    return 0;
}

有任何不懂欢迎私信这个蒟蒻

\huge\mathcal{The\text{ }End}

谢谢管理大大审核^_^