P3306 题解

link，给出 $p$，$a$，$b$，$x_1$，求第一个 $x_i = t$。

$x_{i + 1} \equiv a \times x_i + b \pmod{p}$ 。

$0 \le a, b, x1, t < p$，$2 \le p \le 10^9$， $p$ 为质数。

推一波：

$$X_{i + 1} \equiv a \times X_i + b \pmod{p}$$

$$\Rightarrow X_{i + 1} + \dfrac{b}{a - 1} \equiv a \times X_i + \dfrac{\left(a-1\right)b}{a-1} + \dfrac{b}{a - 1} \pmod{p}$$

$$\Rightarrow X_{i + 1} + \dfrac{b}{a - 1} \equiv a \times X_i + \dfrac{ab}{a - 1} \pmod{p}$$

$$\Rightarrow X_{i + 1} + \dfrac{b}{a - 1} \equiv a \times \left ( X_i + \dfrac{b}{a-1}\right ) \pmod{p}$$

等比数列，直接得到：

$$X_n + \dfrac{b}{a-1} \equiv a^{n - 1} \times \left( X_1 + \dfrac{b}{a - 1} \right) \pmod{p}$$

当 $X_n = t$ 时，只有 $a^{n - 1}$ 未知：

$$a^{n - 1} \equiv \dfrac{t + \dfrac{b}{a-1}}{X_1 + \dfrac{b}{a - 1}} \pmod{p}$$

$\tt{BSGS}$ 即可，不会 $\tt{BSGS}$ 可以康我的另一篇博客，注意要特判 $a=0$ 和 $a=1$ 的情况。

CODE

#include <bits/stdc++.h>
using namespace std;

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? -x : x;
}

#define int long long

int gcd(int a, int b) {
	return (!b ? a : gcd(b, a % b));
}

int Pow(int x, int k, int p, int r = 1) {
	for (; k; k >>= 1, x = x * x % p) {
		if (k & 1) r = r * x % p;
	}
	return r;
}

int inv(int x, int p) {
	return Pow(x % p, p - 2, p);
}

int bsgs(int a, int b, int p) {
	unordered_map<int, int> m;
	b %= p; int t = ceil(sqrt(p));
	for (int i = 0; i < t; i ++) {
		m[Pow(a, i, p) * b % p] = i;
	}
	a = Pow(a, t, p);
	for (int i = 1; i <= t; i ++) {
		int k = Pow(a, i, p);
		if (m.find(k) == m.end()) continue;
		if (i * t - m[k] >= 0) return i * t - m[k];
	}
	return -1;
}

signed main() {
	for (int T = read(); T --;) {
		int p = read(), a = read(), b = read(), X1 = read(), t = read();

		if (X1 == t) puts("1");
		else if (a == 0) (b == t) ? puts("2") : puts("-1");
		else if (a == 1){
			if ((t - X1) % gcd(b, p)) printf("-1\n");
			else printf("%lld\n", ((t - X1) + p) % p * inv(b % p, p) % p + 1);
			continue;
		} else {
			int tmp = b * inv(a - 1, p) % p;
			int res = bsgs(a, (t + tmp) % p * inv(X1 + tmp, p) % p, p);
			printf("%lld\n", (~res ? res + 1 : res));
		}
	}
	return 0;
}

参考：https://www.luogu.com.cn/blog/user17774/solution-p3306 。