洛谷P2303 [SDOI2012] Longge 的问题题解

题目链接：P2303 [SDOI2012] Longge 的问题

题意：

给定一个整数 \(n\)，你需要求出 \(\sum\limits_{i=1}^n \gcd(i, n)\) 。

输入格式：

输入只有一行一个整数，表示 \(n\)。

输出格式：

输出一行一个整数表示答案。

数据范围：

\(1\leq n< 2^{32}\)。

根据数学题套路，我们枚举 \(\gcd(i,n)\) 的值。 \[ \begin{aligned} \sum_{i=1}^n \gcd(i, n) &=\sum_{d \mid n} d \sum_{i=1}^n[\gcd(i, n)=d] \\[6pt]&=\sum_{d \mid n} d \sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\left[\gcd\left(i, \frac{n}{d}\right)=1\right] \\[6pt]&=\sum_{d \mid n} d\cdot \varphi\left(\frac{n}{d}\right) \end{aligned} \] 这个时候其实直接 \(\mathcal{O}\left(d(n)\times\sqrt{n}\right)\) 算就可以了，但还可以更快。

考虑把 \(\varphi(n)\) 拆开（不妨将 \(n\) 唯一分解为 \(\prod_{1 \le i \le m} p_i^{k_i}\) ） \[ n \sum_{d \mid n} \prod_{p \mid d} \frac{p-1}{p} \] 可以发现有很多的 \(d\) 有着相同的贡献。

考虑枚举 \([m]\) 的子集 \(S\) ，它对应的 \(d\) 的个数为 \(\prod_{i \in S}k_i\) ，则它的贡献为 \[ \prod_{i \in S}k_i\cdot\frac{p_i-1}{p_i} \] 现在我们要求的是所有子集的和，因此我们考虑每个 \(p_i\) 的贡献。

先讲一种通俗的题解方法。如下。

不妨记其贡献为 \(\chi_i = k_i\frac{p_i-1}{p_i}\) ，可以发现答案是这么贡献的（例如 \(m=3\) 时） \[ n\times \left(1+\chi_1+\chi_2+\chi_3+\chi_1 \chi_2+\chi_1 \chi_3+\chi_2 \chi_3+\chi_1 \chi_2 \chi_3\right) \] 后面的式子可以化简为 \(\prod(\chi_i+1)\) ，因此答案为 \[ n \prod_{i=1}^{m} \left(k_i\cdot\frac{p_i-1}{p_i} + 1\right) \] 当然这不是一道观察题，其实有更数学的理解，只不过比较难懂。

因为每个 \(p_i\) 的贡献是相互独立的，所以考虑只要每个 \(p_i\) 是否被取。

如果取了，它的贡献就是在原来的答案上乘上一个 \(\chi_i\) ，否则乘上一个 \(e=1\) （单位元）

因此答案为 \[ n \prod_{i=1}^{m} (\chi_i+1) =n \prod_{i=1}^{m} \left(k_i\cdot\frac{p_i-1}{p_i} + 1\right) \] 时间复杂度 \(\mathcal{O}(\sqrt{n})\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int n,t,k,res=1; 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; t = n; // t 用于算 p_i^{-1}
    for(int i=2; i * i <= n; i++)
        if(n % i == 0)
        {
            t /= i; k = 0;
            while(n % i == 0) { ++k; n /= i; }
            res = res * (k * (i - 1) + i);
        }
    if(n != 1) { t /= n; res = res * (2 * n - 1); }
    cout << res * t << '\n';
    return 0;
}

其实还有另一种做法。回到这一步 \[ \sum_{d \mid n} d\cdot \varphi\left(\frac{n}{d}\right) \] 其等价于（其中 \(*\) 表示狄利克雷卷积） \[ \mathrm{id}*\varphi \] 则原函数为积性函数。所以我们可以把原函数 \(f(n)\) 分解为 \(\prod f(p_i^{k_i})\) 。

对于每个形如 \(f(p^c)\) 的式子，可以发现 \[ f(p^c)=\sum_{i=0}^c \varphi\left(p^i\right) p^{c-i} \] 而 \(\varphi(p_i^c) = p^c - p^{c-1}\) 是个经典结论（证明可以直接套 \(\varphi\) 展开公式，得 \(p^c(1-p)\) ）

因此有 \[ \begin{aligned} f\left(p^c\right)&=\sum_{i=0}^c \varphi\left(p^i\right) p^{c-i} \\[6pt]&=p^c+\sum_{i=1}^c\left(p^i-p^{i-1}\right) p^{c-i} \\[6pt]&=p^c+\sum_{i=1}^c\left(p^c-p^{c-1}\right) \\[6pt]&=p^c+c\left(p^c-p^{c-1}\right) \\[6pt]&=(c+1) p^c-c p^{c-1} \end{aligned} \] 因此答案为 \[ f(n)=\prod_{i=1}^{m} f(p_i^{k_i}) = \prod_{i=1}^{m}\left((k_i+1) p^{k_i}-k_i p^{k_i-1}\right) \] 时间复杂度 \(\mathcal{O}(\sqrt{n})\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int n,k,pwd,res=1; 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=2; i * i <= n; i++)
        if(n % i == 0)
        {
            k = 0; pwd = 1;
            while(n % i == 0) { ++k; pwd *= i; n /= i; }
            res = res * ((k + 1) * pwd - k * pwd / i);
        }
    if(n != 1) { res = res * (2 * n - 1); }
    cout << res << '\n';
    return 0;
}