【洛谷题解/SDOI2012】P2303/SDOI2012 D1T1 Longge的问题

-放弃不难，但坚持很酷
-欢迎诸君感受思维与数学的魅力

原题链接：https://www.luogu.com.cn/problem/P2303
难度：提高+/省选-(省选D1T1)
涉及知识点：质因数分解、欧拉函数、思维

题意

求解 $\sum _{i=1}^n\gcd (i,n),n\le 2^{32}$，简明的。

分析与解决

这是一道非常经典的推式子题，我们需要对原式进行一些推导和分析。笔者认为，这道题是很锻炼思维的。

由于笔者也是学习的粉兔的题解，所以本题解将完全复述一遍粉兔的思路，但会加以解释。

对于原式，我们将其转化为：
$$\sum _{j=1}^n(j\times \sum _{i=1}^n[\gcd (i,n)=j])$$
上式的意义为累加一个最大公约数值 $j$ 和$1\sim n$ 中该数值出现的次数的乘积。然后，将上式变换为：
$$\sum _{j=1}^n(j\times \sum _{i=1}^n[\gcd (i/j,n/j)=1](j|i,j|n))$$
上式的意义是进行了一次数学上的变换，然后我们发先 $j$ 乘的个数实际上就是 $i/j$ 和 $n/j$ 互质的数的个数，所以我们可以改写为欧拉函数：
$$\begin{gathered} \sum _{j=1}^n(j\times \phi (n/j)(j|n)) \\ =\sum _{j|n}(j\times \phi (n/j))① \end{gathered}$$
大多数的题解到这一步也就结束了，实际上到这一部分也就可以解题了，令因数个数为 $k$，复杂度为$O(k\sqrt{n})$，可以接受。

但是我们还可以对上式进行化简，我们设一个质数 $p$ 表示 $n$ 的质因子。 继续对 $①$ 式进行变换：
$$\sum _{j|n}(n/j\times \phi (j))$$
然后展开为欧拉函数的公式：
$$\sum _{j|n}(n/j\times (j\times \prod _{p|j}\frac{p-1}{p}))$$
将 $j$ 和它的逆元抵消掉，得：
$$\begin{gathered} \sum _{j|n}(n\times \prod _{p|j}\frac{p-1}{p}) \\ =n\times \sum _{j|n}\prod _{p|j}\frac{p-1}{p} \end{gathered}$$

然后运用唯一分解定理，令 $n=p_1^{b_1}{p}_2^{b_2}{p}_3^{b_3}..p_k^{b_k}.$，并定义 $f_i=\frac{p_i-1}{p_i}$。

那么对于 $n$ 的一个因子 $j$，可以将其表示为 $j=p_1^{c_1}{p}_2^{c_2}{p}_3^{c_3}...p_k^{c_k}(0\le c_i\le b_i)$，那么$\phi (j)=\prod _{p|j}\frac{p-1}{p}=\prod _{i=1}^k{f}_i(c_i>0)$。为什么要保证 $c_i>0$，原因是显然的，如果 $c_i=0$ 则 $j$ 的某个质因子不存在。

我们观察一类 $\prod _{i=1}^k{f}_i(c_i>0)$ 相等的因子 $j,j^{\prime },j^{\prime \prime },...$，它们必须满足在 $i$ 相等的情况下，$c_i$ 同时大于或同时等于 0。因为如果前式相等，则说明这类数的质因子集合是相同的，只是可能 $c_i$ ，即 $p_i$ 的个数不同。基于该结论，我们可以推导出在这类数中，对于一个 $p_i$，要么同时出现，要么同时没有，也就是所谓的 $c_i$ 同时大于或者同时等于 0。

那么这一类数有多少个呢？如果对于属于这类数的 $j$ 有质因子 $p_{q_1},p_{q_2},p_{q_3},...p_{q_g}$，那么显然这类数 $j$ 的答案为 $\prod _{i=1}^g{f}_{q_i}$。令 $b_i$ 为质因子 $p_i$ 的指数，可以得到 $j$ 的质因子个数为 $\prod _{i=1}^g{b}_{q_i}$。那么就可以得到 $j$ 对答案的贡献为 $\prod _{i=1}^g{X}_{q_i}$，$X_i=f_i\times b_i$，也就是某一个 $j$ 的某一个质因子的贡献乘上它的个数。

如果你能坚持看到这里，你一定不难发现每一个质因子的贡献都是独立的，那么最后我们枚举 $n$ 的每一个质因子使用或者不适用，得到最终的答案 $ans$ 为：
$$ans=n\times \prod _{i=1}^k(X_i+1)$$
为什么是 $X_i+1$ 呢，举个例子，如果 $n$ 只有 3 个质因子，那么 $ans$ 为 $n\times (1+X1+X2+X3+X1X2+X1X3+X2X3+X1X2X3)$，将其化简为多项式乘法就是 $n\times (X1+1)(X2+1)(X3+1)$。当然可以类比到质因数个数更多的情况。

如果你能看完这篇文章，我将发自内心地佩服你。

AC代码

#include 
#include 

using namespace std;

typedef long long ll;

ll n;

ll solve ()
{
    ll ans = n;
    for (ll i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            int b = 0;
            while (n % i == 0)
            { //分解质因数
                b++;
                n /= i;
            }
            ans /= i;
            ans *= b * i - b + i;
        }
    }
    if (n > 1)
    {
        ans /= n;
        ans *= n + n - 1;
    }
    return ans;
}

int main()
{
    cin >> n;
    cout << solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

参考资料与后记

粉兔题解：https://www.cnblogs.com/PinkRabbit/p/8278728.html
本文可以视作粉兔题解的注释版（%%%%PinkRabbit），因为笔者在学习数论时其实是较为吃力的，所以我就写下了这篇注释性质的题解供自己以后复习使用也给大家参考。由于本文写作于深夜，如果本文中出现您不理解的地方或者是笔误的地方请联系笔者修改！