CQOI2018 破解D-H协议

题目链接:戳我

BSGS水题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define int long long
using namespace std;
int n,g,p;
map<int,int>ex;
inline int fpow(int x,int y,int mod)
{
    int cur_ans=1;
    while(y)
    {
        if(y&1) cur_ans=1ll*cur_ans*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return cur_ans;
}
inline int inv(int x,int mod){return fpow(x,mod-2,mod);}
inline int bsgs(int a,int b,int mod)
{
    a%=mod,b%=mod;
    int m=ceil(sqrt(mod));
    ex.clear();
    for(int i=0,t=1;i<m;i++,t=1ll*t*a%mod) ex[t]=i;
    for(int i=0,tt=inv(fpow(a,m,mod),mod),cur=b;i<m;i++,cur=1ll*cur*tt%mod)
    {
        if(ex.count(cur))
            return i*m+ex[cur];
    }
    return -1;
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%lld%lld",&g,&p);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        int A,B,a,b;
        scanf("%lld%lld",&A,&B);
        a=(bsgs(g,A,p)+p)%p;
        b=(bsgs(g,B,p)+p)%p;
        printf("%lld
",fpow(g,1ll*a*b%(p-1),p));
    }
    return 0;
}