题意
- 给出递推式如下,求最小的使 \(X_i=G\) 成立的 \(i\)。
分析
- 这里分几种情况来分析:当 \(A=0\) 时,\(X_i\) 要么等于 \(S\),要么等于 \(B\),直接判断即可;当 \(A=1\) 时,\(X_i\) 为等差数列,通项公式为 \(X_i=(S+i\times B)\bmod p\),于是求解同余方程 \(S+i\times B\equiv G\pmod p\) 即可。
- 最后一种情况,当 \(A\ge2\) 时,根据高中的一些知识我们可以知道,这个是可以转化成一个等比数列的。待定系数 \(C\) 有 \(X_i+C\equiv A(X_{i-1}+C)\pmod p\),解得 \(C=(A-1)^{-1}\cdot B\bmod p\)。令 \(Y_i=(X_i+C)\bmod p\),那么 \(Y_i\equiv A^i\cdot Y_0\equiv A^i\cdot(S+C)\pmod p\)。因此原问题转化为关于 \(i\) 的同余方程 \(G+C\equiv A^i\cdot(S+C)\pmod p\) 是否有解和最小正整数解的问题了。这是离散对数问题,利用大步小步算法求解即可。
大步小步算法(BSGS)
- 用于求解形如方程 \(A^x\equiv B\pmod p\) 的离散对数问题,其基于 meet-in-the-middle 的思想,复杂度 \(\tilde{O}(\sqrt n)\)。
- 首先因为 \(A^{x+n(p-1)}\equiv A^x(A^{p-1})^n\equiv A^x\pmod p\),所以如果原方程有解,则在 \([0,n-2]\) 的范围也一定有解。
- 我们拆分 \(x\),令 \(B=\lceil\sqrt p\rceil\),则一定存在 \(0\le L,R\le B\) 使得 \(x=L\cdot B-R\)。此时方程转化为求解 \(0\le L,R\le B\) 满足
- 根据这个式子,我们先预处理出 \(S=\left\{(A^B)^L\bmod p|0\le L\le B\right\}\) 中的所有值,然后对于每一个 \(0\le R\le B\) 计算出 \(B\cdot A^R\bmod p\) 并判断是否在集合 \(S\) 中即可。
代码
#include <bits/stdc++.h>
#define int long long
#define inf 1e10
using namespace std;
int a, b, s, g, p;
int A, B, C;
inline void read(int &x) {
char ch = x = 0;
int m = 1;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + ch - 48;
ch = getchar();
}
x *= m;
return ;
}
inline void print(int x) {
if (x < 0) putchar('-'), x = -x;
static int stk[50];
int top = 0;
do {
stk[top++] = x % 10;
x /= 10;
} while (x);
while (top) {
putchar(stk[--top] + 48);
}
putchar('\n');
return ;
}
inline int ksmi(int a, int b, int p) {
a %= p;
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
inline int BSGS(int a, int b, int p) {
a %= p, b %= p;
if (b == 1 || a == b) return b != 1;
map<int, int> mp;
int B = ceil(sqrt(p)), res = inf;
for (int i = B; i; i--) {
mp[ksmi(a, i * B, p)] = i * B;
}
for (int i = 0; i <= B; i++) {
if (mp.find(b * ksmi(a, i, p) % p) != mp.end()) {
res = min(res, mp[b * ksmi(a, i, p) % p] - i);
}
}
if (res == inf) {
return -1;
} else {
return res;
}
}
signed main() {
int T;
read(T);
while (T--) {
read(p), read(a), read(b), read(s), read(g);
if (s == g) print(0);
else if (a == 0) {
if (b == g) print(1);
else print(-1);
} else if (a == 1) {
if (b == 0) print(-1);
else {
int x = ((g - s) % p + p) % p * ksmi(b, p - 2, p) % p;
print(x);
}
} else if (s == 0 && b == 0) {
print(-1);
} else {
A = a, C = ksmi(A - 1, p - 2, p) * b % p;
B = ksmi(s + C, p - 2, p) * ((g + C) % p) % p;
print(BSGS(A, B, p));
}
}
return 0;
}
标签:le,int,题解,ch,cdot,pmod,ABC270G,equiv,mod
From: https://www.cnblogs.com/iloveoi/p/18037733