扩展欧几里得。
枚举a，根据x1,x3和递推式可得。
(a+1)*b-k*mod=f[3]-a*a*b.
通过扩展欧几里得求出b.
带入原式进行计算。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 20000 + 10;
const int mod = 10001; typedef long long LL; LL f[maxn];
LL n,a,b;
bool ok; LL exgcd(LL a,LL b,LL &x,LL &y) {
if(b==0) {
x=1; y=0;
return a;
}
LL d=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return d;
} int main() {
scanf("%lld",&n);
for(int i=1;i<=n*2;i+=2) scanf("%d",&f[i]);
for(a=0;a<=10000;a++) {
ok=1;
LL t=f[3]-a*a*f[1],x,y;
LL d = exgcd(mod,a+1,x,b);
if(t%d) continue;
b=b*(t/d);
for(int i=2;i<=2*n;i++) {
if(i&1) {
if(((a*f[i-1]+b)%mod)!=f[i] ) {
ok=0;
break;
}
}
else f[i]=(a*f[i-1]+b)%mod;
}
if(ok) break;
}
for(int i=2;i<=2*n;i+=2) printf("%lld\n",f[i]);
return 0;
}