UVA 12169 Disgruntled Judge 扩展欧几里得

/**
题目：UVA 12169 Disgruntled Judge
链接：https://vjudge.net/problem/UVA-12169
题意：原题
思路：
a,b范围都在10000以内。暴力枚举1e8；但是还要判断。所以时间不够。

如果可以枚举a，然后算出b，再判断可行性，那么时间上是可行的。但是是多次方的方程无法解。

想其他办法：
xi = (a*xi-1 + b) % 10001 

xi+1 = (a*xi+b)%10001

xi+2 = (a*xi+1+b)%10001

=> xi+2 = a*(a*xi+b)+b % 10001 
        = a*a*xi + (a+1)*b % 10001

   xi+2 = a*a*xi + (a+1)*b - 10001*k ;  扩展欧几里得求解b。 

  (a+1)*b - 10001*k = xi+2 - a*a*xi;  因为mod=10001所以，求出任意一个解即可。 哪怕b是负数，+一个mod也是可以变成非负数的。

a*x + b*y = c;  c%gcd(a,b)==0;

a*1 + b*0 = a;

*/

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long ll;
const int maxn = 1e4+100;
ll c[maxn];
int T;
const int mod = 1e4+1;
void ext_gcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    if(!b) {d = a; x = 1; y = 0;}
    else{
        ext_gcd(b,a%b,d,y,x); y = y-x*(a/b);
    }
}
bool judge(ll a,ll b)
{
    for(int i = 1; i < T; i++){
        ll t = (a*a*c[i-1] + (a+1)*b+mod) % mod;
        if(t!=c[i]) return false;
    }
    return true;
}
int main()
{
    //freopen("C:\Users\Administrator\Desktop\in.txt","r",stdin);
    //freopen("C:\Users\Administrator\Desktop\out.txt","w",stdout);
    while(scanf("%d",&T)==1)
    {
        for(int i = 0; i < T; i++){
            scanf("%lld",&c[i]);
        }
        if(T==1){
            printf("0
");
            continue;
        }
        ll a, b, d, x, y;
        for(int i = 1; i < T; i++){
            for(a = 0; a < mod; a++){
                ll temp = c[i]-a*a*c[i-1];
                ext_gcd(a+1,mod,d,x,y);
                b = x*(temp/d);
                if(b<0) b+= mod;
                if(judge(a,b)){
                    break;
                }
            }
        }
        for(int i = 0; i < T; i++){
            printf("%lld
",(a*c[i]+b+mod)%mod);
        }
    }
    return 0;
}