//数据是有多水 连 10^10的枚举都能过
关于拓展欧几里德:大概就是x1=y2,y1=x2-[a/b]y2,按这个规律递归到gcd(a,0)的形式,此时公因数为a,方程也变为a*x+0*y=gcd(a,0)的形式,显然解为x=1,y=0,然后再递归回去就能得到解(a*x+b*y=gcd(a,b)的解)
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<string> using namespace std; long long T;
long long x[]; void exGED(long long a,long long b,long long &d,long long &x,long long &y){
if (b==){
x=;
y=;
d=a;
}
else{
exGED(b,a%b,d,x,y);
long long tmp=x;
x=y;
y=tmp-(a/b)*y;
}
} bool solve(long long a){
long long d,b,k;
long long tmp=x[]-a*a*x[];
exGED(a+,,d,b,k);
if (tmp%d!=) return false;
b=b*(tmp/d);
for (long long i=;i<=*T;i++){
if (i%==){
x[i]=(x[i-]*a+b)%;
}
else{
if (x[i]!=((x[i-]*a+b)%)){
return false;
}
}
}
for (long long i=;i<=*T;i+=){
printf("%I64d\n",x[i]);
}
return true;
} int main(){
scanf("%I64d",&T);
for (long long i=;i<*T;i+=){
scanf("%I64d",&x[i]);
}
//solve(1096);
for (long long a=;a<=;a++){
if (solve(a)) break;
}
return ;
}
/*
3
17
822
3014
*/