给定 、、、，现有一数列
求最小的 满足 。
链接
题解
令 ，得
当 时
否则，设
令 代入得
未知量只有左边 的指数，使用 BSGS 求出即可。
代码
#include <cstdio>
#include <cmath>
#include <map>
inline void exgcd(long long a, long long b, long long &g, long long &x, long long &y) {
if (!b) g = a, x = 1, y = 0;
else exgcd(b, a % b, g, y, x), y -= x * (a / b);
}
inline long long inv(long long x, long long p) {
long long g, res, tmp;
exgcd(x, p, g, res, tmp);
return (res % p + p) % p;
}
inline long long bsgs(long long a, long long b, long long p) {
a %= p;
b %= p;
/*
long long tmp = 1;
for (int i = 1; i <= p; i++) {
if (tmp == b) return i - 1;
tmp = tmp * a % p;
}
return -1;
*/
std::map<long long, long long> map;
long long m = ceil(sqrt(p)), t = 1;
for (int i = 0; i < m; i++) {
if (!map.count(t)) map[t] = i;
t = t * a % p;
}
long long k = inv(t, p), w = b;
for (int i = 0; i < m; i++) {
if (map.count(w)) return i * m + map[w];
w = w * k % p;
}
return -1;
}
inline long long solve(long long p, long long a, long long b, long long x1, long long t) {
if (t == x1) return 1;
else if (a == 0) return b == t ? 2 : -1;
else if (a == 1) {
if (!b) return -1;
return ((((t - x1) % p + p) % p) * inv(b, p) % p) + 1;
} else {
long long q = inv(1 - a + p, p);
long long d = (((t - b * q) % p + p) % p) * inv(((x1 - b * q) % p + p) % p, p);
long long ans = bsgs(a, d, p);
if (ans == -1) return -1;
else return ans + 1;
}
}
inline long long force(int p, int a, int b, int x1, int t) {
if (a == 1) {
if (!b) return -1;
return ((((t - x1) % p + p) % p) * inv(b, p) % p) + 1;
}
/*
int x = x1;
for (int i = 1; i <= p; i++) {
// printf("a[%d] = %d\n", i, x);
if (x == t) return i;
x = (a * x + b) % p;
}
return -1;
*/
long long q = inv(1 - a + p, p), ai = 1;
/*
for (int i = 1; i <= p; i++) {
long long x = (ai * (((x1 - b * q) % p + p) % p) + b * q % p) % p;
// printf("a[%d] = %lld\n", i, x);
if (x == t) return i;
ai = (ai * a) % p;
}
return -1;
*/
long long tmp = (((t - b * q) % p + p) % p) * inv(((x1 - b * q) % p + p) % p, p) % p;
for (int i = 1; i <= p; i++) {
if (ai == tmp) return i;
ai = (ai * a) % p;
}
return -1;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int p, a, b, x1, t;
scanf("%d %d %d %d %d", &p, &a, &b, &x1, &t);
printf("%lld\n", solve(p, a, b, x1, t));
}
}