P1447:[NOI2010]能量采集题解

解法

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

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

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

继续阅读P1447:[NOI2010]能量采集题解

P1829:[国家集训队]Crash 的数字表格题解

主要思路

首先规定,\(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\)成为唯一的两个互质因子。

继续阅读P1829:[国家集训队]Crash 的数字表格题解

P3327:[SDOI2015]约数个数和题解

主要思路和推导

这道题还是比较有意思的(啊呀看了好久的题解才会写,真菜),主要就是把\(d\)转换成了:

\[ d(xy) = \sum_{i|x}^x \sum_{j|y}^y [\gcd(i,j) = 1] \]

可以感性理解一下:每一次约数被枚举出来的时候,只有互质的情况下才会被计数,避免了重复计数。 继续阅读P3327:[SDOI2015]约数个数和题解