koishi的数学题

题目描述

Koishi 在 Flandre 的指导下成为了一名数学大师，她想了一道简单的数学题。

输入一个整数 $n$，设 $\displaystyle f(x) = \sum_{i=1}^n x \bmod i$，你需要输出 $f(1), f(2), \ldots , f(n)$。

按照套路，Koishi 假装自己并不会做这道题，就来求你帮忙辣。

输入格式

一个正整数 $n$。

输出格式

一行用空格分隔的 $n$ 个整数 $f(1), f(2), \ldots , f(n)$。

样例 #1

样例输入 #1

10

样例输出 #1

9 16 22 25 29 27 29 24 21 13

提示

对于 $20\%$ 的数据，$n \le 1000$。  
对于 $60\%$ 的数据，$n \le 10^5$。  
对于 $100\%$ 的数据，$1 \le n \le 10^6$。

解题思路

  这几天在洛谷跳题，结果很多不会做qwq。

  对于 $x \bmod i$，关键是要想到可以转换为 $x - \left\lfloor \dfrac{x}{i} \right\rfloor \cdot i$，因此就有

\begin{align*}
f(x) &= \sum\limits_{i=1}^{n}{x \bmod i} \\
&= \sum\limits_{i=1}^{n}{x - \left\lfloor \dfrac{x}{i} \right\rfloor \cdot i} \\
&= n \cdot x - \sum\limits_{i=1}^{n}{\left\lfloor \dfrac{x}{i} \right\rfloor \cdot i}
\end{align*}

  接下来可以考虑递推，假设我们已经知道了 $f(x)$ 中 $\sum\limits_{i=1}^{n}{\left\lfloor \dfrac{x}{i} \right\rfloor \cdot i}$ 这部分的结果，考虑能否推出 $\sum\limits_{i=1}^{n}{\left\lfloor \dfrac{x+1}{i} \right\rfloor \cdot i}$ 的结果。分以下两种情况考虑：

1. $x \bmod i < i - 1$：那么有 $\left\lfloor \dfrac{x+1}{i} \right\rfloor \cdot i = \left\lfloor \dfrac{x}{i} \right\rfloor \cdot i$。
2. $x \bmod i = i - 1$：那么有 $\left\lfloor \dfrac{x+1}{i} \right\rfloor \cdot i = \left(\left\lfloor \dfrac{x}{i} \right\rfloor + 1 \right) \cdot i = \left\lfloor \dfrac{x}{i} \right\rfloor \cdot i + i$。

  即如果 $i$ 是 $x+1$ 的约数，那么 $\left\lfloor \dfrac{x+1}{i} \right\rfloor \cdot i$ 就会比 $\left\lfloor \dfrac{x}{i} \right\rfloor \cdot i$ 多出 $i$，否则相等。因此对于整个 $\sum\limits_{i=1}^{n}{\left\lfloor \dfrac{x+1}{i} \right\rfloor \cdot i}$ 的结果，就会比 $\sum\limits_{i=1}^{n}{\left\lfloor \dfrac{x}{i} \right\rfloor \cdot i}$ 多出 $x+1$ 的约数和。

  所以对于 $x \in [1,n]$，我们可以对每个 $x$ 的分解约数求约数和，但这样的时间复杂度为 $O(n \sqrt{n})$。为此我们可以反过来枚举约数 $i \in [1,n]$，再枚举所有不超过 $n$ 的 $i$ 的倍数 $j$，那么这些 $j$ 的都含有约数 $i$，时间复杂度就是 $O(\sum\limits_{i=1}^{n}{\frac{n}{i}}) \approx O(n \log{n})$。

  AC 代码如下：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

LL s[N];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            s[j] += i;
        }
    }
    LL last = 0;
    for (int i = 1; i <= n; i++) {
        printf("%lld ", 1ll * i * n + last - s[i]);
        last -= s[i];
    }
    
    return 0;
}

参考资料

  题解 P3708 【koishi的数学题】：https://www.luogu.com.cn/blog/asuldb/solution-p3708