这次这道题目还是关于扩展欧几里得的题目，如果对扩展欧几里得算法不熟悉的话可以看我前面的文章。

题目传送门

题意

题意就是有一个公式x[i]=(a*x[i-1]+b) mod 10001,给你一半的数组，x[1],x[3],x[5]等等，你要通过这些数字算出正确的另一半的数组。

转化

首先我们肯定会先在x[i]=(ax[i-1]+b) mod 10001上面做文章，我们可以将x[i-1]=(ax[i-2]+b) mod 10001放到前一个式子中，我们就可以得到x[i]=(aax[i-2]+(a+1)b) mod 10001,然后我们会发现这个mod真是非常地碍眼，所以我们不如把式子变式成x[i]-aax[i-2]=10001(-k)+(a+1)b,其实就是加了个10001的倍数而已（因为是取模嘛）。这个式子看起来就舒服多了，我们只要求出k和b就成功了。

减少未知变量

那么该怎么求出a和b呢，有人可能会想到，我们既然有这么多个已知点，我们不如多拿出几组来变成方程组，然后我们就可以求出k和b了。这种想法固然可以，但是因为这个方程的未知数有三个（a,k,b），而且a还有个平方，这就是一个三元二次方程啊，化简推公式恐怕会把自己绕进去，那么我们可不可以减少一个变量呢？

答案是可以的，我们可以看到所有的数组中数字都是经过mod 10001过的，那么我们的a一定能在小于10001的数字中找到答案，所有我们完全可以发挥计算机的优势，我们枚举次数最高的a变量，然后自己手动算出其余的两个变量。

求解

这下我们能否使用普通的解方程的方法进行求解呢？其实这道题应该还是可以使用方程组求解的，只不过需要注意细节：
1.k和b必须得是整数，需要检查。
2.2.求出来的根要对其他的x适用，需要一一检查。
其实我们对于求解整数解有另一个办法——使用扩展欧几里得。根据ax+by=gcd(a,b),我们可以知道本来的a就是10001，b就是a+1，x和y就是我们想要求解的a和b，我们根据这四个量求出g，然后我们根据（x[i]-aax[i-2]）%g==0就可以知道有解

这里再放一下扩展欧几里得的模板：

ll extend_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;y=0;
        return a;
    }else{
        ll r=extend_gcd(b,a%b,y,x);
        y-=x*(a/b);
        return r;
    }
}

然后我们就可以根据扩展欧几里得算出
k=k（x[i]-aax[i-2]）/g
b=b（x[i]-aax[i-2]）/g
当然这里的b和k都是经过extend_gcd引用更新过的。这样我们就可以算出k和b了，之后就是验证和计算剩余部分的代码了，由于比较简单这里不赘述了，下面放完整代码。

代码

#include <iostream>
using namespace std;
const int N=210;
typedef long long ll;

ll x[N];

ll extend_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;y=0;
        return a;
    }else{
        ll r=extend_gcd(b,a%b,y,x);
        y-=x*(a/b);
        return r;
    }
}

int main(){
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n){
        for(int i=1;i<=2*n;i+=2)
            cin>>x[i];
        ll k,b;
        for(ll a=0;a<=10001;a++){
            ll t=x[3]-a*a*x[1];
            ll g=extend_gcd(10001,a+1,k,b);
            if(t%g)
                continue;
            k=k*t/g;
            b=b*t/g;
            bool flag=true;
            for(int i=2;i<=2*n;i++){
                if(i%2==1&&(x[i]!=((a*x[i-1]+b)%10001))){
                    flag= false;
                    break;
                }else
                    x[i]=(a*x[i-1]+b)%10001;
            }
            if(flag)
                break;
        }
        for(int i=2;i<=2*n;i+=2)
            cout << x[i] << endl;
    }
    return 0;
}

In The End

UVA12169题：不爽的裁判（扩展欧几里得求解不定方程）

题目传送门

题意

转化

减少未知变量

求解

代码