【CQOI2018】破解破解D-H协议

佚名 4年前 (2020-01-17) 随笔 1888人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

分析：

　　已知$g^a=A$和$g^b=B$，求$g^{ab}\bmod P$，可以先求$a$，再得$B^a$。

　　也即，在$g^a\equiv A\pmod P$中求$a$。显然$BSGS$。

　　$g$是原根，这就意味着$g^t\bmod P\;(0\leq t<P)$取遍了$[0,P)$，考虑枚举指数找到$a$。

　　如何加速？考虑一种拆分方法使得可以预处理一部分，即设$t=i\times m-j$，移项，得到$g^{i\times m}\equiv A\times g^j\pmod P$。可以发现，当$m=\lceil\sqrt{P}\,\rceil$时有最优复杂度。

　　预处理：算出所有$g^{i\times m}$插入到桶里（使用$STL-map$）。使用容器之后要注意常数。

实现（100分）：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define IL inline
#define RG register
#define _1 first
#define _2 second
using namespace std;
typedef long long LL;

    LL g,p,m;
    
IL LL qpow(LL a,LL b){
    LL ret=1;
    while(b>0){
        if(b&1)
            ret=ret*a%p;
        a=a*a%p;
        b>>=1;
        
    }
    
    return ret;
    
}
    
    map<LL,LL>s;
IL void init(){
    m=sqrt(p)+1;
    LL t=1,x=qpow(g,m);
    for(LL i=1;i<=m;i++){
        t=t*x%p;
        s[t]=i*m;
        
    }
    
}

IL LL calc(LL t){
    for(int i=0;i<m;i++){
        if(s.find(t)!=s.end())
            return s[t]-i;
        t=t*g%p;
        
    }
    return 0;
    
}

int main(){
    scanf("%lld%lld",&g,&p);
    init();
    
    int T;
    scanf("%d",&T);
    while(T--){
        LL a,b;
        scanf("%lld%lld",&a,&b);
        printf("%lld\n",qpow(b,calc(a)));
        
    }

    return 0;

}