P1447:「NOI2010」能量采集题解

解法

这道题是一道裸题，考察莫比乌斯反演和 Dirichlet 卷积的知识。

在这里我们规定\(n<m\)，这两者调换不会对答案产生影响。然后我们来观察这个计数规律，发现每一个点对答案的贡献至少为\(1\)，附加的贡献其实就是当前线段上除了本身的整点（整数坐标点）个数的两倍，换句话说就是：

\[ ans = \sum_{i = 1}^n \sum_{j = 1}^m 1 + 2( gcd(i, j) – 1 ) \]

题意就是要求：

\[ ( \sum_{i = 1}^n \sum_{j = 1}^n ij gcd(i, j) ) \mod p \]

言简意赅的题面非常舒适。出现了\(gcd\)可以考虑往反演方面思考。先进行例行的套路：枚举\(gcd\)。在这里为了书写方便，我就把取模省去。

省选级别以上的 OI 赛事中的数学题，相比于 NOIp 的数学题来说要难很多。这篇文章我来记录学习了莫比乌斯反演和杜教筛之后的一些心得。以下是本文大纲：

给定一个式子\(x^2 \equiv n \pmod p\)，求\(x\)的值。其中，如果\(x\)有解，则称\(n\)为\(p\)的二次剩余。

首先，强烈推荐阅读这篇文章。（看懂了就不用来了）

Miller-Robin 算法包括两个部分，一个是费马测试，还有一个就是二次探测。这两个东西听上去非常的玄学（的确也是），我来讲清楚，并附上代码。我们现在要进行测试的数是\(p\)。

首先规定，\(N<M\)。之后写出统计答案的式子：

\[ \sum_{i=1}^N \sum_{j=1}^M lcm(i,j) \\ \sum_{i=1}^N \sum_{j=1}^M \frac{ij}{\gcd(i,j)} \]

然后我们可以试着去枚举最大公约数\(gcd(i,j)=d\)，然后让\(i,j\)成为唯一的两个互质因子。