题目链接

 

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分):

【CQOI2018】破解破解D-H协议 随笔 第1张
#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;

}
View Code

 

 

小结:

  高级枚举方法get√