首先本题直接暴力枚举a，b可解，最坏为1秒左右时间可解出（一个test文件需要的时间）
高效算法为枚举a，然后由x1,x3,解出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);
本人较懒只写出了认为gcd（a+1，MOD）==1在所有时刻成立的版本 ；
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
void gcd(LL a,LL b,LL& d,LL& x,LL& y){
if(!b){d=a; x=1; y=0;}
else {gcd(b,a%b,d,y,x); y-=x*(a/b);}
}
const int MOD = 10001;
const int maxn = 101;
LL ans[maxn*3],te[maxn*3];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=2*n;i+=2){
scanf("%lld",&ans[i]);
}
int lim = 2*n;
LL x,y,g;
bool flag =false;
for(int a=0;a<MOD;a++){
gcd(a+1,MOD,g,x,y);
LL c =ans[3] - ans[1]*a*a;
if(c%g!=0) continue;
LL b=x*c/g;
te[1]=ans[1];
int ok=1;
for(int i=2;i<=lim;i++){
te[i]=(te[i-1]*a+b)%MOD;
if((i&1) && te[i] != ans[i]){
ok=false; break;
}
}
if(ok){ flag=true; break; }
}
for(int i=2;i<=lim;i+=2){
printf("%d\n",te[i]);
}
return 0;
}