M_sea

洛谷4454 [CQOI2018]破解D-H协议
LuoguBZOJ分析$\begin{cases}g^a\equiv A\pmod{P}\\g^b\equiv B...
扫描右侧二维码阅读全文
15
2019/03

洛谷4454 [CQOI2018]破解D-H协议

Luogu

BZOJ

分析

$\begin{cases}g^a\equiv A\pmod{P}\\g^b\equiv B\pmod{P}\end{cases}$

直接上$\mathrm{BSGS}$求出 $a$ 和 $b$ ,然后答案就是 $g^{ab}\mod P$ 。

然后指数要对 $P-1$ 取膜而不是 $P$ ,因为 $\varphi(P)=P-1$ 。

代码

//It is made by M_sea
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int g,mod;

inline int qpow(int a,int b) {
    int ans=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) ans=1ll*ans*a%mod;
    return ans;
}


inline int bsgs(int a,int b) {
    unordered_map<int,int> hash; hash.clear();
    b%=mod; int t=sqrt(mod)+1;
    for (re int i=0,j=1;i<t;++i,j=1ll*j*a%mod) hash[1ll*b*j%mod]=i;
    a=qpow(a,t);
    if (!a) return (b==0)?1:-1;
    for (re int i=0,j=1;i<=t;++i,j=1ll*j*a%mod) {;
        int k=hash.find(j)==hash.end()?-1:hash[j];
        if (k>=0&&i*t-k>=0) return i*t-k;
    }
    return -1;
}

int main() {
    g=read(),mod=read(); int T=read();
    while (T--) {
        int A=read(),B=read();
        int a=bsgs(g,A),b=bsgs(g,B);
        printf("%d\n",qpow(g,1ll*a*b%(mod-1)));
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 12 PM

发表评论