解法
首先我们在\(Q\)的剩余系内枚举数\(x_0\),对于此每个数表示成\(x = (x_0 + k * P) \mod Q\),思考一下发现这些数会随着\(k\)变化,且这些数会呈现周期性规律:也就是这些数在一个环上,我们可以考虑记录\(Q\)剩余系中每一个数在\(P\)中的贡献,记录成前缀和,计算答案时比较排名来判断环的方向(长弧或是短弧)。
具体看代码吧,细细品味一下应该就能理解了。
首先我们在\(Q\)的剩余系内枚举数\(x_0\),对于此每个数表示成\(x = (x_0 + k * P) \mod Q\),思考一下发现这些数会随着\(k\)变化,且这些数会呈现周期性规律:也就是这些数在一个环上,我们可以考虑记录\(Q\)剩余系中每一个数在\(P\)中的贡献,记录成前缀和,计算答案时比较排名来判断环的方向(长弧或是短弧)。
具体看代码吧,细细品味一下应该就能理解了。
这道题是一道裸题,考察莫比乌斯反演和 Dirichlet 卷积的知识。
在这里我们规定\(n<m\),这两者调换不会对答案产生影响。然后我们来观察这个计数规律,发现每一个点对答案的贡献至少为\(1\),附加的贡献其实就是当前线段上除了本身的整点(整数坐标点)个数的两倍,换句话说就是:
\[ ans = \sum_{i = 1}^n \sum_{j = 1}^m 1 + 2( gcd(i, j) – 1 ) \]
一开始毫无头绪,在看了题解之后豁然开朗(废话,看了题解不都豁然开朗么)。题目中要求我们求出:
\[ ans = \underbrace{ \sum_{a_1 = L}^R \dots \sum_{a_n = L}^R }_{n \text{ 个}} [\gcd_{i = 1}^n (a_i) = k] \]
题意就是要求:
\[ ( \sum_{i = 1}^n \sum_{j = 1}^n ij gcd(i, j) ) \mod p \]
言简意赅的题面非常舒适。出现了\(gcd\)可以考虑往反演方面思考。先进行例行的套路:枚举\(gcd\)。在这里为了书写方便,我就把取模省去。
省选级别以上的 OI 赛事中的数学题,相比于 NOIp 的数学题来说要难很多。这篇文章我来记录学习了莫比乌斯反演和杜教筛之后的一些心得。以下是本文大纲:
好题。
我们首先写出这道题的暴力解:
\[ answer = \sum_{i = 1}^n \sum_{j = 1}^m \sigma_1 (gcd(i, j)) [\sigma_1 (gcd(i, j)) \leq limit] \]
复杂度超级大,怎么办?换一种思维来写这个式子,考虑枚举每一个\(gcd(i, j)\)为\(d\),记起次数为\(g(d)\),我们可以搞出并化简为: