我們可以暴力枚舉a,然后通過x1和x3確定b的值，然后確定其他的數字，一旦出現錯誤就放棄這組解。

關鍵問題就在于如何通過a,x1,x3確定b的值

x2 = ( x1 * a + b) % M
x3 = ( x2 * a + b ) % M = ( ( x1 * a + b ) % M * a + b ) % M
x3 - k * M = x1 * a % M * a % M + b * a % M + b
我們不妨設b<M
b * ( a + 1 ) + k * M = x3 - x1 * a * a
我們想要求出b，即就是求出這個二元一次方程的一組解，這時候用擴展歐幾里得算法就可以解決。（雖然他的原理我還沒有搞懂）

可是寫出來以后我卻一直連樣例都過不了，經過一個多小時的探索，我發現，爆longlong了，你永遠不知道哪里會爆long long，無語。

得到的經驗，凡是對空間復雜度要求不是很高又有乘法的運算還是盡量用long long ，可以避免爆long long 而引發的錯誤。
經過反復調試，我終于在沒有用long long 的情況下做出了這道題（心酸）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cctype>
#include<queue>
#include<set>using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=105;
const int MOD=10001;
int a1[MAXN],a2[MAXN];
int n;
int a,b;
int c,t,p,q,k;void gcd_ojbk(int a,int b,int& d,int& x,int& y)
{if(!b){d=a; x=1; y=0;}else{gcd_ojbk(b,a%b,d,y,x);y-=x*(a/b); }
}int main()
{scanf("%d",&n);for(ll i=1;i<=n;i++){scanf("%d",&a1[i]);}for(a=0;a<MOD;a++){bool flag=true;t=a+1;p=(a1[2]-a1[1]*a%MOD*a%MOD+MOD)%MOD;gcd_ojbk(MOD,t,q,c,k);if(p%q) continue;b=((k*(p/q)%MOD+MOD)%MOD);	//這里很容易爆long long a2[1]=(a*a1[1]%MOD+b)%MOD;for(int i=2;i<=n;i++){if((a*a2[i-1]%MOD+b)%MOD!=a1[i]){flag=false;break;}a2[i]=(a*a1[i]%MOD+b)%MOD;}if(flag){for(int i=1;i<=n;i++){printf("%d\n",a2[i]);}break;}}return 0;
}