#### UVa 12169 – Disgruntled Judge [扩展欧几里得/暴力]

x3 = (a*a*x1 + a*b) % 10001 + b % 10001, 化简为：x3 – 10001k = a*a*x1 + b*(a+1)，再化简为：b*(a+1) + 10001*k = x3-a*a*x1。

```#include <bits/stdc++.h>
using namespace std;

const int mod = 10001;
int n, v[205];

void solve() {
for(int a = 0; a < mod; ++a) {
for(int b = 0; b < mod; ++b) {
int i;
for(i = 2; i <= 2*n; ++i) {
if(i & 1) {
if(v[i] != (a * v[i-1] % mod + b) % mod)
break;
}
else v[i] = (a * v[i-1] % mod + b) % mod;
}
if(i == 2 * n + 1) {
for(i = 2; i <= 2*n; i += 2)
printf("%d\n", v[i]);
return;
}
}
}
}

int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &v[2*i-1]);
solve();
return 0;
}
```

```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 10001;
ll n, v[205];

// ax + by = gcd(a, b) = g;
void exgcd(ll a, ll b, ll &g, ll &x, ll &y) {
if(!b) { g = a; x = 1; y = 0; }
else { exgcd(b, a%b, g, y, x); y -= x*(a/b); }
}

bool judge(ll a, ll b) {
for(int i = 2; i <= 2*n; ++i) {
if(i & 1) {
if(v[i] != (v[i-1] * a % mod + b) % mod)
return false;
}
else v[i] = (v[i-1] * a % mod + b) % mod;
}
return true;
}

int main() {
scanf("%lld", &n);
for(int i = 1; i <= n; ++i)
scanf("%lld", &v[2*i-1]);
for(ll a = 0; a < mod; ++a) {
ll b, k, g, c = v[3]-a*a*v[1];
exgcd(mod, a+1, g, k, b);
if(c % g) continue;
b = b * c / g;
if(judge(a, b % mod)) {
for(int i = 2; i <= 2*n; i += 2)
printf("%lld\n", v[i]);
break;
}
}
return 0;
}
```