题解来源：http://8.136.99.126/discuss/675d20a8ab50bce9d824eb64

下面令 $k=y,b=x$，$a$ 数组下标为 $0\sim n-1$，则

$$\sum_{i=0}^{n-1} (ki + b - a_i)^2\\ = \sum_{i=0}^{n-1} (k^2i^2 + b^2 + a_i^2 + 2kbi - 2kia_i - 2ba_i)\\ = k^2 \sum_{i=0}^{n-1} i^2 + nb^2 + \sum_{i=0}^{n-1} a_i^2 + 2kb \sum_{i=0}^{n-1} i - 2k \sum_{i=0}^{n-1} ia_i - 2b \sum_{i=0}^{n-1} a_i $$

设：

$$A = \sum_{i=0}^{n-1} i^2$$ $$B = \sum_{i=0}^{n-1} i$$ $$C = \sum_{i=0}^{n-1} ia_i$$ $$D = \sum_{i=0}^{n-1} a_i$$

则只需最小化：

$$Ak^2 + nb^2 + 2kBb - 2kC - 2Db\\ =nb^2+(2kB-2D)b+Ak^2-2kC $$

这是一个关于 $b$ 的二次函数，显然当 $b = \dfrac{D - kB}{n}$ 时取得最小值，将 $b$ 用 $k$ 表示，得：

$$Ak^2 + nb^2 + 2kBb - 2kC - 2Db\\ = Ak^2 + \frac{(D - kB)^2}{n} + \frac{2kB(D - kB)}{n} - 2kC - \frac{2D(D - kB)}{n} $$$$= Ak^2 + \frac{-D^2 - B^2k^2 + 2BDk}{n} - 2kC$$ $$= \frac{nAk^2 - 2nCk - D^2 - B^2k^2 + 2BDk}{n}$$ $$= \frac{(nA - B^2)k^2 + (2BD - 2nC)k - D^2}{n}$$

这也是一个关于 $k$ 的二次函数，显然当 $k = \dfrac{nC - BD}{nA - B^2}$ 时取得最小值。直接计算即可，时间复杂度 $O(n)$。

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define req(i,a,b) for(int i(a);i>=(b);--i)
using namespace std;
int n,xx;
double a,b,c,d,x,y;
signed main()
{
    cin>>n;
	rep(i,0,n-1) cin>>xx,a+=i*i,b+=i,c+=i*xx,d+=xx;
	y=(c*n-b*d)/(a*n-b*b),x=(d-b*y)/n;
	printf("%.6lf %.6lf",x,y);
	return 0;
}