Problem
传送门
给定\(g,P,A,B\),其中\(P\)为质数
并且满足:
\(g^a=A\ \ mod\ \ P\)
\(g^b=B\ \ mod\ \ P\)
求\(g^{a*b}\)
Solution
又是知道板子直接A系列……
用到了BSGS(大步小步法)……
还是介绍一下吧……
BSGS主要用来解决\(A^x\equiv B\ (\ mod\ C)\)已知\(A,B,C\)(其中\(C\)为质数)求\(x\)。
具体实现其实还挺好理解的
令\(D = A^\sqrt {C}\)
通过枚举\(i\)我们有:
\(D^i*A^{x_0}\equiv B\ (\ mod\ C)\)
有没有一种熟悉的感觉？
表示没有
由于\(D^i,B,C\)都是已知数，所以我们可以通过解同余方程得到一个解\(X\),然后判断\(X\)是否可表示为\(A^{x_0}\)这种形式……
那么只需在预处理时用\(map/hash\)将\(A^i,i∈[1,\sqrt C]\)存下来即可。
对于这道题：
知道了BSGS的话直接粘板子，稍微改一下就可以A了……
上代码:
Code
#include <bits/stdc++.h>
using namespace std;
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
inline int read(){
int res = 0, fl = 1;
char r = getchar();
for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
const int Maxn = 1e5;
map <int,short> Map;
int g[Maxn],G[Maxn], mod, n;
int Pow(int a, int b){
int mul = 1;
while(b){
if(b & 1) mul = 1ll * mul * a % mod;
a = 1ll * a * a % mod;
b = b >> 1;
}
return mul;
}
void init(){
n = sqrt(mod - 1) + 1, G[0] = g[0] = 1;
for (int i = 1; i <= n; ++i) g[i + 1] = 1ll * g[i] * g[1] % mod;
for (int i = 0; i <= n; ++i) Map[g[i]] = i + 1;
G[1] = g[n];
for (int i = 1; i <= n; ++i) G[i + 1] = 1ll * G[i] * G[1] % mod;
}
int solve(int A){
for (int i = 0; i <= n; ++i){
int inv = Pow(G[i],mod - 2);
int xz = 1ll * inv * A % mod;
//printf("%d %d %d\n",xz, Map[xz], i * n + Map[xz] - 1);
if(Map[xz]) return i * n + Map[xz] - 1;
}
return 0;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#endif
g[1] = read(), mod = read();
int Q = read();
init();
while(Q--){
int x = solve(read());
printf("%d\n",Pow(read(), x));
}
return 0;
}
转载于:https://www.cnblogs.com/LZYcaiji/p/10574639.html
相关资源：JAVA上百实例源码以及开源项目
