首先知道：
\[E_i = \sum_{j = 1}^{i – 1}\frac{q_j}{(i – j)^2} – \sum_{j = i + 1}^{n}\frac{q_j}{(i – j)^2} \]
现在要求所有的。我们可以考虑分成前后两个部分分别计算。先考虑前面的部分：
\[a_i = \sum_{j = 1}^{i – 1}\frac{q_j}{(i – j)^2}\]
我们发现这一部分还是很好计算的：当多项式指数为\(i\)时，对应\(a_i\)，发现\(q_j\)和\((i – j)^2\)的下标相加恰好为\(i\)。正好是卷积的形式。后面那一个部分也可以直接这样算。
真你妈毒瘤。
原式子是长这个样子的：
\[ f(n) = \sum_{i = 0}^n \sum_{j = 0}^i \begin{Bmatrix} i \\ j \end{Bmatrix} 2^j (j!) \]
这道题是一道裸题，考察莫比乌斯反演和 Dirichlet 卷积的知识。
在这里我们规定\(n<m\)，这两者调换不会对答案产生影响。然后我们来观察这个计数规律，发现每一个点对答案的贡献至少为\(1\)，附加的贡献其实就是当前线段上除了本身的整点（整数坐标点）个数的两倍，换句话说就是：
\[ ans = \sum_{i = 1}^n \sum_{j = 1}^m 1 + 2( gcd(i, j) – 1 ) \]
省选级别以上的 OI 赛事中的数学题，相比于 NOIp 的数学题来说要难很多。这篇文章我来记录学习了莫比乌斯反演和杜教筛之后的一些心得。以下是本文大纲：