UVA 12169 Disgruntled Judge（Extended_Euclid）

用扩展欧几里德Extended_Euclid解线性模方程，思路在注释里面了。

注意数据范围不要爆int了。

/*********************************************************
*      --------------Tyrannosaurus---------              *
*   author AbyssalFish                                   *
**********************************************************/
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;


/*
取模可以说是个不定方程
如果x3 和 x1满足递推关系，则有
a^2*x1 + (a+1)*b = x3 mod m
(a+1)*b + m * k = x3 - a^2*x1

枚举a,则b和k未知, extended_Euclid
求出一组解 (a+1)*x0 + m*y0 = d
d = gcd(a+1, m)是最小正线性组合，(不包括0,0
对于其他任意的线性组合的和为c， 都是d的倍数，系数(x0 y0)* (c/d)
b在模m意义下唯一

O(T*m)
*/

int ex_euclid(int a, int b, int &x, int &y)
{
    if(!b){
        x = 1; y = 0;
        return a;
    }else {
        int d = ex_euclid(b, a%b, y, x);
        y -= a/b*x;
        return d;
    }
}

const int mod = 10001, maxn = 105;
int dat[maxn];
int n;

bool check(int a,int &b)
{
    int x,y;
    int d = ex_euclid(mod, a+1, x, y);
    int aa = a*a%mod, c = (dat[1]-aa*dat[0])%mod;
    if( (c) % d) return false;
    b = c/d*y % mod; //这里要按mod^3算,看见/d自动脑补成了mod^2...
    c = (a+1)*b%mod;
    for(int i = 1; i < n; i++){
        if( (aa*dat[i-1]+c - dat[i])%mod ) {
            return false;
        }
    }
    if(b < mod) b += mod;
    return true;
}

//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d",dat+i);
    int a, b;
    for(a = 0; a < mod; a++){
        if(check(a,b)) {
            for(int i = 0; i < n; i++){
                printf("%d
", (a*dat[i]+b)%mod);
            }
            break;
        }
    }
    return 0;
}