{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 x2010501 的文章《【求解模线性方程】》','https://www.xiaopingtou.net/article-51761.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
题目链接 HDU2769
UVA12169
【题意】
【分析】
如果不看上面的分析，最先想到的肯定枚举a和b，因为最多只有100个数字，又只有一组数据，UVA3000ms这样肯定可以过，但在HDU1000ms，如果写的戳一点就过不了了(判断合法写好了肯定可以过，本渣渣想不到)，然后只能按照书上的，只枚举a，而b直接用模方程计算出来(因为都是取模运算，不能直接用方程解，一开始这样写的，后来突然发现了)；
那么就剩下怎样计算出b了；
首先可以得出:
x[2]≡a*x[1]+b (mod 10001); x[3]≡a*x[2]+b (mod 10001);
然后把x[2]带入第二个等式得到 x[3]≡a^2 * x[1]+(a+1)b (mod 10001);
移项得(a+1)b≡x[3]-a^2x[1] (mod 10001);
这样其实就得到了一个形如ax≡b (mod n);的模方程了，接下来就是求解模方程了,具体看代码注释；
【AC CODE】0ms(HDU) 15ms(UVA)
【分析】
如果不看上面的分析，最先想到的肯定枚举a和b，因为最多只有100个数字，又只有一组数据，UVA3000ms这样肯定可以过，但在HDU1000ms，如果写的戳一点就过不了了(判断合法写好了肯定可以过，本渣渣想不到)，然后只能按照书上的，只枚举a，而b直接用模方程计算出来(因为都是取模运算，不能直接用方程解，一开始这样写的，后来突然发现了)；
那么就剩下怎样计算出b了；
首先可以得出:
x[2]≡a*x[1]+b (mod 10001); x[3]≡a*x[2]+b (mod 10001);
然后把x[2]带入第二个等式得到 x[3]≡a^2 * x[1]+(a+1)b (mod 10001);
移项得(a+1)b≡x[3]-a^2x[1] (mod 10001);
这样其实就得到了一个形如ax≡b (mod n);的模方程了，接下来就是求解模方程了,具体看代码注释；
【AC CODE】0ms(HDU) 15ms(UVA)
/*
枚举a求b，模方程:x[3]≡a^2 * x[1]+ab+b (mod 10001)
由"a≡b(mod n)使得a-b是n的倍数"，令倍数为y，则 (a+1)b+10001y = x[3]-a^2 * x[1];
此时可以直接用扩展GCD求出b和y;因为题意说输出任意一个满足的即可，所以只要求出0~10000中一个b
*/
#include
#include
#include
#define MAXN 105
#define MOD 10001
int in[MAXN],ans[MAXN],n;
void e_gcd(int a, int b, int& d, int& x, int& y)
{
if(!b) d = a, x = 1, y = 0;
else e_gcd(b,a%b,d,y,x), y -= a/b*x;
}
void sloved()
{
for (int a = 0; a <= 10000; a++)
{
int c = (in[1]-(a*a%MOD)*in[0]%MOD+MOD)%MOD,d,b,y;
e_gcd(a+1,-MOD,d,b,y);
if(c%d) continue;//无解
b *= c/d;//任意一个b
//求出0~10000中最小的b
int gb = abs(-MOD/d);
b = (b%gb+gb)%gb;
for (int j = 0; j < n; j++)
{
ans[j] = (a*in[j]%MOD+b)%MOD;
if(j == n-1)
{
for(int i = 0; i < n; i++)
printf("%d
", ans[i]);
return;
}
if((a*ans[j]%MOD+b)%MOD != in[j+1]) break;
}
}
}
int main()
{
#ifdef SHY
freopen("e:\1.txt","r",stdin);
#endif
scanf("%d%*c", &n);
for(int i = 0; i < n; i++)
scanf("%d%*c", &in[i]);
sloved();
return 0;
}