加密通话
题目背景
如果您急于 AK 后过元旦，请直接看简化题面。
“哔哔啵啵…哔哔哔……啵~”此起彼伏的电报声在机房回响（不要问为什么会有电报。）。
啊，$\text{RenaMoe}$ 在通信！
显示器上蓝灯、绿灯、红灯，你不让我，我不让你，都闪满了灯赶趟儿。红的像火，绿的像草，蓝的像天。灯里带着迷影，闭了眼，显示屏上仿佛已经满是灯儿、字儿、$OIer$（——改变自老舍的《春》）。
嗯？上面的字怎么读不通？
$\text{RenaMoe}$：因为我们用了加密通话！
哇，这也太厉害了！那您怎么知道对方发的信息是什么意思呢？
$\text{RenaMoe}$：是这样的，首先我会先和对方预定好一个模数 $p$，和模 $p$ 的一个原根 $g$（当成一个数就行）。
$\text{RenaMoe}$：然后我将我的信息编辑成数字信息 $x$，然后向他发送加密后的信息 $R$，其中 $R=g^x\mod p$。
$\text{RenaMoe}$：接着我会接受对方回复的信息 $L$，同样 $L=g^y\mod p$，$y$ 就是对方回复的信息。
$\text{RenaMoe}$： 接着我会将 $y$ 求出，然后计算 $M=R^y\mod p$ 作为下一次通信的加密密钥。同样，对方会计算 $M=L^x\mod p$。
$\text{RenaMoe}$：因为我们得到的答案都是：$M=g^{xy}\mod p$ 所以我们都可以得到下一次通讯加密密钥。
哇，这太聪明了！
$\text{RenaMoe}$：但是，这种方式并不能有效的保证通讯秘密。由于我们的通话信息可以被同一个人读取，也就是说你可以同时知道 $L,R$，如果你还知道我们提前预设的 $g$ 和 $p$。
$\text{RenaMoe}$：然后你可通过这个可以计算出 $M$ 就可以知道我们下一次的通话信息呢！
真的么？那要怎么做呢？
$\text{RenaMoe}$：“$@!##*!…#%!@#$”（加密交流）。
奥，那我现在就试试！
$\text{RenaMoe}$:（\托腮）。
解析完毕：$\text{RenaMoe}$：我今天中午想吃 $banana$，你可以帮我带亿点点吗？
简化题面
现在有 $L=g^y\mod p,R=g^x\mod p$，请求出 $M=g^{xy}\mod p$。
输入
第一行两个数 $g$ 和 $p$。
第二行一个数 $n$。
后面有 $n$ 行，每行两个数：$L,R$。
输出
输出 $n$ 行，代表每次破解的 $M$。
样例 $1$
读入
11 23
2
4 7
1 20
输出
8
1
样例 $2$
读入
50 59
3
26 13
12 14
14 15
输出
25
7
5
样例 $3$
读入
31 71
5
62 30
12 54
43 37
65 57
37 47
输出
45
57
32
54
45
样例 $4$
读入
2780303 9613367
3
8199460 8916560
9376676 3921108
2576481 4520467
输出
8302437
8872205
5937276
数据范围
- $10\%:$
$1 \le n \le 10$
$2\le L,R < P < 1e3$
- $30\%:$
$1 \le n \le 20$
$2\le L,R < P < 1e8$
- 另 $10\%:$
$2\le L=R < P < 1e8$
- $100\%:$
$1 \le n \le 200$
$2\le L,R < P < 1e8$
对于各个范围内的 $g$ 保证一定存在且是原根。$p$ 一定是一个质数。
题解
本题是一个 BSGS 的板子题。
通过 BSGS 求出 $y$。
计算 $M\mod p$ 输出即可。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<string>
#include<cmath>
#include<map>
#include<vector>
using namespace std;
long long r_r(){
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
map<long long,long long>h_h;
long long k_m(long long a,long long b,long long m_d){//快速幂
long long r_s=1;
while(b){
if(b&1)r_s=(r_s*a)%m_d;
a=(a*a)%m_d;
b>>=1;
}
return r_s;
}
long long b_g(long long a,long long b,long long m_d){//BSGS
h_h.clear();
int s_z=ceil(sqrt(m_d));
long long b_s=b%m_d;
h_h[b_s]=0;
for(int i=1;i<=s_z;i++){
b_s=b_s*a%m_d;
h_h[b_s]=i;
}
b_s=k_m(a,s_z,m_d);
long long t_p=1;
for(long long i=1;i<=s_z;i++){
t_p=t_p*b_s%m_d;
if(h_h[t_p])
return((i*s_z-h_h[t_p])%m_d+m_d)%m_d;
}
return-1;
}
int main(){
long long g=r_r(),m_d=r_r();
long long n=r_r();
while(n--){
long long a_i=r_r(),b_i=r_r();//读取每次的 L,R
long long k=b_g(g,a_i,m_d);//通过其中一个计算 x 或了另一个计算 y
printf("%lld\n",k_m(b_i,k,m_d));//计算 M
}
return 0;
}
