这题并不难只是需要把题读懂 — By ShadderLeave
一句话题意
给定两个数 \(p\)和\(g\)，有\(t\)组询问，每组询问给出\(A\)和\(B\)
其中 A = \(g^a \bmod p\) B = \(g^b \bmod p\)
问你\(g^{ab} \bmod p\)是多少。
初步解法就是用BSGS求出每个\(a\),\(b\)在用快速幂算出\(g^{ab} \bmod p\)
可实际上你就会发现只要算一个就行。
算出\(a\)直接求出\(B^a \bmod p\)就是答案
然鹅，就这样交上去你就会狂TLE
所以，我们只能再考虑优化。
每次询问，我们都会把map清空，并重新储存，但这样会浪费很多时间，那我们从这开始优化
我们要求的是这个柿子 \(g^a \equiv A\)
我们利用BSGS的思想可以把它化为 \(g^{kt+b} \equiv A\)
也就是\(g^{kt} \equiv A \times g^B\)
发现方程右边会随A的取值发生变化，但左边的g和t确定了，那么值就不会变。
所以，我们可以预先处理出\(g^{kt}\)并把他插入map中。
对于每组询问，枚举\(A \times g^j\) 看在map中是否出现过。
如果出现过，答案就是 map中的存的幂指数 - \(j\)
但有一个很大的问题就是：
卡 。。。常 。。。。
卡。。。。。常。。。。
卡。。。。。。常。。。。。
毒瘤出题人nmsl
所以我们只能少用快速幂，再求\(g^{kt}\)以及\(g^j\)只能用累乘的方法来求。
出题人我*****
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
#define LL long long
int g,t,p,A,B;
map<LL,int> hash;
inline LL read()
{
LL s = 0, w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s= s * 10+ch - '0'; ch = getchar();}
return s * w;
}
LL ksm(LL a,LL b)
{
LL res = 1;
for(; b; b >>= 1)
{
if(b & 1) res =res * a % p;
a = a * a % p;
}
return res;
}
void YYCH()//预处理出g^kt
{
LL t = sqrt(p) + 1;
LL base = ksm(g,t); LL tmp = 1;
for(int i = 1; i <= t; i++)
{
tmp = tmp * base % p;//累乘避免被卡常
hash[tmp] = i * t;
}
}
LL BSGS(int k)
{
LL t = sqrt(p) + 1; LL tmp = k;
if(hash[tmp]) return hash[tmp];
for(int i = 1; i < t; i++)//枚举A*g^j
{
tmp = tmp * g % p;
if(hash[tmp]) return hash[tmp] - i;
}
// return -1;
}
int main()
{
g = read(); p = read(); t = read(); YYCH();
while(t--)
{
A = read(); B = read();
printf("%lld\n",ksm(B,BSGS(A)));
}
return 0;
}
我拿出我珍藏多年的卡常火车头，出题人（17张牌你能秒杀我）你要是能卡住我，我当场把屏幕吃掉。
呜呜，我错了，放过我吧，不要再卡我了。