P1891 疯狂 LCM

P1891 疯狂 LCM

$$
\begin {array} {c}
& \displaystyle \sum _ {i = 1} ^ n lcm (i, n) \\
\Longrightarrow & \displaystyle \sum _ {i = 1} ^ n \frac {in}{(i, n)} \\
\Longrightarrow & \displaystyle n\sum _ {i = 1} ^ n \frac i {(i, n)} \\
\Longrightarrow & \displaystyle n\sum _ {d | n} \sum _ {i = 1} ^ n \frac i d [(i, n) = d] \\
\Longrightarrow & \displaystyle n\sum _ {d | n} \sum _ {i = 1} ^ n \frac i d [(\frac i d, \frac n d) = 1] \\
\Longrightarrow & \displaystyle n\sum _ {d | n} \sum _ {i = 1} ^ {\frac n d} i [(i, \frac n d) = 1] \\
\Longrightarrow & \displaystyle n\sum _ {d | n} \sum _ {i = 1} ^ d i [(i, d) = 1] \\
\Longrightarrow & \displaystyle n\sum _ {d | n} \sigma (d) \\
\end {array}
$$

注意到 $\forall d > 1, \sigma (d) = \frac {d \varphi(d)} 2$ ，可以枚举 $d$ 在 $O(\sqrt n)$ 时间内回答。

但是不够优。

记 $f (n) = \displaystyle \sum _ {d | n} \sigma (d)$ ，显然 $f$ 是一个积性函数，可以筛。

对于质数 $n$ ，
$$
f(n) = \sigma (1) + \sigma(n) = 1 + (1 + 2 + \ldots n - 1) = 1 + n(n - 1)
$$
对于质数的若干次幂，
$$
f (n) = \sigma(1) + \sigma(p) + \ldots + \sigma (p ^ k) = f (\frac n p) + \sigma (p ^ k)
$$
其中，
$$
\begin {aligned}
\sigma (p ^ k) &= (1 + 2 + \ldots + p ^ k) - (p + 2p + \ldots + p ^ k) \\
&= \frac {p ^ k(p ^ k + 1)} 2 - p \frac {p ^ {k - 1} (p ^ {k - 1} + 1)} 2 \\
&= \frac {p ^ {2k} - p ^ {2k - 1}} 2 \\
\end {aligned}
$$
那么
$$
\sigma (p ^ {k - 1}) = \frac {p ^ {2k - 2} - p ^ {2k - 3}} 2
$$
有
$$
\sigma (p ^ k) = p ^ 2 \sigma (p ^ {k - 1})
$$
所以
$$
f(n) = f(\frac n p) + p ^ 2 (f(\frac n p) - f(\frac n {p ^ 2}))
$$
这样就可以做线性筛了。

查看代码

#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n;
int cnt;
LL p[N], low[N], f[N];
void init()
{
    f[1] = 1;
    low[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (!low[i])
        {
            p[++cnt] = i;
            f[i] = (LL)i * i - i + 1;
            low[i] = i;
        }
        for (int j = 1; j <= cnt && i * p[j] < N; j++)
        {
            if (i % p[j] == 0)
            {
                if (low[i] == i)
                    f[i * p[j]] = f[i] + (f[i] - f[i / p[j]]) * p[j] * p[j];
                else
                    f[i * p[j]] = f[i / low[i]] * f[p[j] * low[i]];
                low[i * p[j]] = low[i] * p[j];
                break;
            }
            f[i * p[j]] = f[i] * f[p[j]];
            low[i * p[j]] = p[j];
        }
    }
}
int main()
{
    init();
    int T;
    scanf("%d", &T);
    for (int n; T; T--)
    {
        scanf("%d", &n);
        printf("%lld\n", (LL)n * (f[n] + 1) / 2);
    }
    return 0;
}