洛谷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;
}