题意：随机选取x1,a,b，根据公式xi=(a*xi-1+b)%10001得到一个长度为2*n的序列，奇数项作为输入，求偶数项，若有多种，随机输出一组答案。
思路：a和b均未知，可以考虑枚举a和b，时间复杂度为10000*10000*100，但是题目数据比较水，这样枚举也是能过的。高效的做法是：枚举a，根据以下公式求出b。
a*x1+b - MOD*y1 = x2;
a*x2+b - MOD*y2 = x3;
解得：
x3 - a*a*x1=(a+1)*b + MOD * y;
该方程为关于变量b的模线性方程 ，用扩展欧几里得算法解出一个解b0，（当gcd（a+1，MOD）==1） 则解出的为一个同余系；
b = b0 + MOD*k (k为任意整数)；（该方程对应了 b = b0 + MOD' * k ,其中MOD' 为MOD/ gcd（a+1，MOD） ）; 只需要检验一个b即可
但是当gcd（a+1，MOD）不等1时，直接用b0求解是有问题的因为解不在是MOD的同余系而是MOD‘的同余系；
所以正解应该是算出b0然后解出0 - 10000范围内的 可行b 然后检验； 算法复杂度为 O(nlogn*100);
#include<stdio.h>
#include<string.h>
const int mod=;
typedef long long ll;
ll x[];
ll ex_gcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=,y=;
return a;
}
int ans=ex_gcd(b,a%b,y,x);
y-=a/b*x;
return ans;
}
int main(){
int n,i;
while(~scanf("%d",&n)){
n*=;
for(i=;i<n;i+=){
scanf("%lld",&x[i]);
}
long long a,b,c,d,y;
for(a=;;a++){
c=x[]-a*a*x[];
d=ex_gcd(a+,mod,b,y);
if(c%d) continue;
b=b*c/d;
for(i=;i<=n;i++){
if(i&){
if(x[i]!=(a*x[i-]+b)%mod)
break;
}else
x[i]=(a*x[i-]+b)%mod;
}
if(i>n) break;
}
for(i=;i<=n;i+=)
printf("%lld\n",x[i]);
}
return ;
}