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

· · 题解

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

不要看这道题题目长而且是紫题就放弃，只要读懂题目就不难了。

题目大意

给定质数 P，和模 P 意义下的数 g，和一个正整数 n。

接下来给出 n 组数据 每组数据一行两个整数 A 和 B，其中 A=g^a\ mod\ P，B=g^b\ mod\ P，求 g^{ab}\ mod\ P 的值。

这是一道的求高次同余方程的题，看似是要求两个方程，其实思考一下就可以发现只要算出一个方程就可以了。因为两条式子获得的是一样的 K，所以我们只需要用 BSGS 算法求其中一个方程的解，然后用快速幂输出就可以了。

BSGS 模板题

My code

#include<cstdio>
#include<cmath>
#include<map>

using namespace std;

#define ll long long //好习惯

ll g,p,n,A,B,qwq; //qwq表示其中一个方程的解
map<ll,ll>k; //hash表

ll qpow(ll a,ll b,ll p){
    ll e=1;
    while(b){
        if(b&1)e=e*a%p;
        b>>=1;
        a=a*a%p;
    }
    return e%p;
} //快速幂模板

ll BSGS(ll a,ll b,ll p){
    k.clear(); //hash表初始化
    ll m=ceil(sqrt(p)),ans;
    for(ll i=0;i<=m;i++){
        if(!i){
            ans=b%p;
            k[ans]=i;
            continue;
        }
        ans=(ans*a)%p;
        k[ans]=i;
    }
    ll t=qpow(a,m,p);
    ans=1;
    for(ll i=1;i<=m;i++){
        ans=(ans*t)%p;
        if(k[ans]){
            ll o=i*m-k[ans];
            return (o%p+p)%p; //返回答案
        }
    }
    return -1;
} // BSGS模板

int main(){
    scanf("%lld %lld",&g,&p);
    scanf("%lld",&n);
    while(n--){
        scanf("%lld %lld",&A,&B);
        qwq=BSGS(g,A,p);
        printf("%lld\n",qpow(B,qwq,p)); // 输出答案
    }
    return 0;
}