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

题目

https://www.luogu.com.cn/problem/P4454

杂题乱做ing...

思路

首先我们把式子列一下:

\(g^a\equiv A(mod P)\)

\(g^b\equiv B(mod P)\)

求\(g^{ab}\)

g是原根，那是不是要用到一些高妙的数论性质呀。。。然后我们看一眼式子，发现只要把\(a\)和\(b\)求出来就行了，也就是求\(A\)和\(B\)在模\(P\)意义下的离散对数。

这不就是个BSGS裸题嘛，为什么能评成紫题啊。。。

代码（伪）

点击查看代码

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

map<int,int> H;

ll kasumi(ll x,ll p,ll m){

    ll ans=1,base=x;

    for(;p;p>>=1){

        if(p&1) ans=ans*base%m;

        base=base*base%m;

    }

    return ans;

}

ll BSGS(ll a,ll b,ll p){

    int i;

    H.clear();

    ll k=(ll)(sqrt(p)+1);

    ll ak=1;

    H[b]=0;

    for(i=1;i<k;++i){

        ak=ak*a%p;

        H[(int)(ak*b%p)]=i;

    }

    ak=ak*a%p;

    ll t=1;

    for(i=1;i<=k;++i){

        t=t*ak%p;

        if(H.count((int)t)){

            int z=H.find((int)t)->second;

            return i*k-z;

        }

    }

}

int main(){

    int T;

    ll g,P;

    ll a,b,A,B;

    ll ans;

    scanf("%lld%lld",&g,&P);

    scanf("%d",&T);

    while(T--){

        scanf("%lld%lld",&A,&B);

        a=BSGS(g,A,P);

        b=BSGS(g,B,P);

        ans=kasumi(g,a*b%(P-1),P);

        printf("%lld\n",ans);

    }

    // system("pause");

    return 0;

}

喜闻乐见卡map，然后我们自己写个哈希表，这题就水完了。

代码（真）

点击查看代码

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#define ll long long

#define zzd 233333

using namespace std;

struct Hashmap{

    int fst[zzd],nxt[1<<16],cnt;

    struct data{

        int x,y;

    } d[1<<16];

    void clear(){

        cnt=0;

        memset(fst,0,sizeof(fst));

        memset(nxt,0,sizeof(nxt));

    }

    int insert(int t1,int t2){

        d[++cnt].x=t1;

        d[cnt].y=t2;

        nxt[cnt]=fst[t1%zzd];

        fst[t1%zzd]=cnt;

    }

    int find(int t){

        int i=fst[t%zzd];

        while(i&&d[i].x!=t) i=nxt[i];

        if(i) return d[i].y;

        else return -1;

    }

} H;

ll kasumi(ll x,ll p,ll m){

    ll ans=1,base=x;

    for(;p;p>>=1){

        if(p&1) ans=ans*base%m;

        base=base*base%m;

    }

    return ans;

}

ll BSGS(ll a,ll b,ll p){

    int i;

    H.clear();

    ll k=(ll)(sqrt(p)+1);

    ll ak=1;

    H.insert(b,0);

    for(i=1;i<k;++i){

        ak=ak*a%p;

        H.insert((int)(ak*b%p),i);

    }

    ak=ak*a%p;

    ll t=1;

    for(i=1;i<=k;++i){

        t=t*ak%p;

        int z=H.find((int)t);

        if(z>=0) return i*k-z;

    }

}

int main(){

    int T;

    ll g,P;

    ll a,b,A,B;

    ll ans;

    scanf("%lld%lld",&g,&P);

    scanf("%d",&T);

    while(T--){

        scanf("%lld%lld",&A,&B);

        a=BSGS(g,A,P);

        b=BSGS(g,B,P);

        ans=kasumi(g,a*b%(P-1),P);

        printf("%lld\n",ans);

    }

    // system("pause");

    return 0;

}

巴特西

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

题目

思路

代码（伪）

代码（真）

最新文章

热门文章