链接：

 

题意：

有个裁判出的题太难，总是没人做，所以他很不爽。有一次他终于忍不住了，

心想：“反正我的题没人做，我干嘛要费那么多心思出题？不如就输入一个随机数，输出一个随机数吧。”

于是他找了3个整数x1、a和b，然后按照递推公式xi = (a * x(i-1) + b) mod 10001计算出了一个长度为2T的数列，

其中T是测试数据的组数。然后，他把T和x1, x3,…, x(2T-1)写到输入文件中，x2, x4,…, x(2T)写到了输出文件中。

你的任务就是解决这个疯狂的题目：输入T, x1, x3,…, x(2T-1)，输出x2, x4,…, x(2T)。

输入保证T≤100，且输入的所有x值为0～10000的整数。如果有多种可能的输出，任意输出一个即可。

 

分析：

由题意可得（下面的M为10001，k,k1,k2为任意整数）：

x2 = a * x1 + b - k1 * M;

x3 = a * x2 + b - k2 * M;

联立上面两式得 M * k + (-a - 1) * b = a * a * x1 - x3;

所以我们可以枚举a，然后用拓展欧几里德求出b和其他值，再判断可行性即可。

 

代码：

1 #include 
     
       2  3 typedef long long int LLI; 4 const LLI M = 10001; 5 int T; 6 LLI x[100*2+5]; 7  8 void exgcd(LLI m, LLI a, LLI& g, LLI& k, LLI& b) { // 拓展欧几里德 9     if(!a) g = m, k = 1, b = 0;10     else exgcd(a, m%a, g, b, k), b -= k * (m/a);11 }12 13 bool judge(LLI a) {14     LLI g, k, b, t = a * a * x[1] - x[3];15     exgcd(M, -a-1, g, k, b);16     if(t % g) return false;17     b *= t / g;18     for(int i = 2; i <= 2 * T; i++) {19         LLI j = (a * x[i-1] + b) % M;20         if(i & 1) {21             if(x[i] != j) return false;22         } else x[i] = j;23     }24     return true;25 }26 27 int main() {28     scanf("%d", &T);29     for(int i = 1; i < 2 * T; i += 2) scanf("%lld", &x[i]);30     for(LLI a = 0; a < M; a++) if(judge(a)) break;31     for(int i = 2; i <= 2 * T; i += 2) printf("%lld\n", x[i]);32     return 0;33 }