题目大意：有3个整数 x[1], a, b 满足递推式x[i]=(a*x[i-1]+b)mod 10001。由这个递推式计算出了长度为2T的数列，现在要求输入x[1],x[3],......x[2T-1], 输出x[2],x[4]......x[2T]. T<=100,0<=x<=10000. 如果有多种可能的输出，任意输出一个结果即可。
由于a和b都小于等于10000，直接枚举a和b暴力可以过。但是有没有更快的方法呢？
首先令递推式的i=2，那么x[2]=(a*x[1]+b)mod 10001；再令i=3，得x[3]=(a*x[2]+b)mod 10001，可以得出x[3]=(a*(a*x[1]+b)+b)mod 10001。这时候只有a和b是变量，我们枚举a，就可以求出b了。(a+1)*b mod 10001 = ( (x[3]-a*a*x[1]) mod 10001 + 10001 ) mod 10001.(这里的x[3]-a*a*x[1]可能为负，代码中可以先不取模，后面计算b的时候一起取模即可) 所以简化成(a+1)*b mod 10001 = (x[3]-a*a*x[1]) mod 10001。这里就变成了同模方程，扩展欧几里得即可解答。
暴力代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; const int maxn=+;
const int mod=;
int in[maxn]; int main()
{
//freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
for(int i=; i<t; i++)
scanf("%d",in+i);
bool flag;
for(int a=; a<=; a++)
{
for(int b=; b<=; b++)
{
flag=false;
for(int i=; i<t; i++)
if(in[i]!=((a*(a*in[i-]%mod+b)+b)%mod))
{
flag=true;
break;
}
if(!flag)
{
for(int i=; i<t; i++)
printf("%d\n",(a*in[i]+b)%mod);
break;
}
}
if(!flag)
break;
}
return ;
}
扩展欧几里得：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; const int maxn=+;
const int mod=;
int in[maxn];
typedef long long ll; ll exgcd(ll a, ll b, ll&x, ll&y)
{
if (b == )
{
x = ;
y = ;
return a;
}
ll r = exgcd(b, a%b, y, x);
ll t = x;
y = y - a/b*t;
return r;
}
int main()
{
//freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
for(int i=; i<t; i++)
scanf("%d",in+i);
bool flag;
for(ll a=; a<=; a++)
{
ll x,y; //定义long long 型是保证没有取模的式子不会超内存
ll g=exgcd(a+,mod,x,y);
ll tmp=in[]-a*a*in[]; //这里可以先不取模，后面计算b的时候取模
if(tmp%g==)
{
flag=false;
ll b=(x*tmp/g)%mod; //这里最好取下模，虽然后面计算in[i]的时候也会取模，但是算出来的in[i]可能因为b负太多而变成负数
for(int i=;i<t;i++)
{
if(in[i]!=(a*(a*in[i-]+b)+b)%mod)
{
flag=true;
break;
}
}
if(!flag)
{
for(int i=;i<t;i++)
printf("%d\n",(a*in[i]+b)%mod);
break;
}
} }
return ;
}