这个题没有那么麻烦，实际上来说是有一些奇怪的，因为在你听完之后你会感到这个题真的是非常非常的简单。
怎么说呢，由上面那个递推公式：
那么一定有
$X_2 = (A \times X_1 + B) ~ mod ~ 10001$
$X_3 = (A \times X_2 + B) ~ mod ~ 10001$
那么显然我们可以把这两个式子合起来，也就是：
化简一下：
那么假设我们知道了A，因为我们一定知道$X_1$, $X_3$，就可以根据上面这个式子直接知道B，那么转而来看A的数据范围，只有1000，也就是说假设我只是简单地枚举A时间也是够的。
于是我们枚举A然后推出B，然后就可以在$O(TA)$的时间复杂度内取得可行解。
当然在处理的时候我们仍然需要考虑到逆元。
至于如何判断该解可行，你只需要奇偶一起推，当你推出来的奇数序号的数和输入有悖时，这个A就是不可行的咯。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
using namespace std ;
typedef long long LL ;
const LL MAXN = 10010 ;
const LL MAXM = 100010 ;
const LL INF = 0x7fffffff ;
const LL Mod = 10001 ;
LL T, B, X[MAXN], F = 1, Y[MAXN], Inv[MAXN] ;
inline LL Read() {
LL X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
return X * F ;
}
inline LL Exgcd(LL A, LL B, LL & X, LL & Y) {
if (! B) { X = 1, Y = 0 ; return A ; }
else {
LL Ans = Exgcd(B, A % B, X, Y) ;
LL Tmp = X ; X = Y ; Y = Tmp - (A / B) * Y ;
return Ans ;
}
}
inline LL Init(LL A) {
LL X, Y ;
LL Tmp = Exgcd(A, Mod, X, Y) ;
X /= Tmp ; X = (X % Mod + Mod) % Mod ;
return X ;
}
int main() {
T = Read() ;
for (LL i = 1 ; i <= 10001 ; i ++) Inv[i] = Init(i) ;
for (LL i = 1 ; i <= 2 * T ; i += 2) X[i] = Read() ;
Y[1] = X[1] ;
for (LL A = 0 ; A <= 10001 ; A ++) {
F = 1 ;
B = ((X[3] - A * A *X[1]) % Mod + Mod) % Mod ;
B = B * Inv[A + 1] % Mod ;
for (LL i = 2 ; i <= 2 * T ; i ++) {
if (i % 2 == 1) {
Y[i] = (A * Y[i - 1] + B) % 10001 ;
if (Y[i] != X[i]) {
F = 0 ;
break ;
}
} else
Y[i] = (A * Y[i - 1] + B) % 10001 ;
}
if (F == 1) {
for (LL i = 2 ; i <= 2 * T ; i += 2)
printf("%lld\n", Y[i]) ;
return 0 ;
}
}
}