Uva12169（扩展欧几里得）
题意：
已知 $x_i=(a*x_{i-1}+b) mod 10001$，且告诉你 $x_1,x_3.........x_{2t-1}$, 让你求出其偶数列
解法：
令$ x_2=(ax_1+b)mod 10001$，$x_3= (ax_2+b)mod 10001$
解得：$x_3+10001k=a^{2}x_1+( a + 1) b$
移像得：$x_3 - a^{2}x_1=( a + 1) b - 10001k$
把 $b$ 和$（-k）$看成是未知数，这就是求解一个 $ax+by=c$ 的方程，扩展欧几里得可解
见代码
/*
由于a的范围只有1e5，所以我们可以直接枚举a的所有值，
然后根据公式求出b的值，之后根据a和b的值递推所有的原数列的值
期间会用到扩展欧几里得解线性方程组
如果有不一样的，说明就不存在，重来
*/
#include<cstdio>
using namespace std;
typedef long long ll;
const int mod = ;
ll f[*], n; //扩展欧几里得解线性方程组
ll exgcd(ll a, ll b, ll &x, ll &y){
if (b == ){
x = , y = ;
return a;
}
ll r = exgcd(b, a%b, x, y);
ll t = x;
x = y;
y = t - a / b*y;
return r;
} inline bool linear_equation(ll a, ll b, ll c, ll &x, ll &y){
ll d = exgcd(a, b, x, y);
if (c%d) return false;
ll k = c / d;
x *= k; y *= k; //求得的只是其中一组解
return true;
} bool check(ll a,ll b) {
for (int i = ; i <= n * ; i++) {
ll now = (a*f[i - ] + b) % mod;
if (i & ) {
if (now == f[i]) continue;
else return false;
}
else f[i] = now;
}
return true;
} int main() {
scanf("%d", &n);
for (int i = ; i <= n * ; i += ) scanf("%lld", &f[i]);
for (ll a = ; a <= ; a++) {
ll b, k;
if (!linear_equation(a + , mod, f[] - a*a*f[], b, k))continue;
if (check(a, b)) break;
}
for (int i = ; i <= * n; i+=) {
printf("%lld\n", f[i]);
}
return ;
}