第十三届蓝桥杯省赛JavaA组 H 题，JavaC组 I 题—— 因数平分和 (AC)

1. 因数平分和

1.题目描述

记 $f(x)$ 为 $x$ 的所有因数的平方的和。例如: $f(12)=1^2+2^2+3^2+4^2+6^2+12^2$

定义 $g(n)={\sum }_{i=1}^{n}f(i)$ 。给定 $n$, 求 $g(n)$ 除以 $10^9+7$ 的余数。

2.输入格式

输入一行包含一个正整数 nn 。

3.输出格式

输出一个整数表示答案 $g(n)$ 除以 $10^9+7$ 的余数。

4.样例输入

100000

5.样例输出

680584257

6.数据范围

$1\le n\le 10^9$

7.原题链接

因数平方和

2.解题思路

根据定义可知 $g(n)=f(1)+f(2)+f(3)+...+f(n)$。对于任意的 $f(i)$，其值为它所有的因数的平方和累加， 反过来想，对于任意一个数 $i$ ，在$[1,n]$中有多少个数是 $i$ 的倍数，则 $i^2$ 则会被累加几次。

根据倍数的原理我们可知：
对于范围$[1,n]$中是 1 的倍数的个数为 $\lfloor \frac{n}{1}\rfloor$个；
对于范围$[1,n]$中是 2 的倍数的个数为 $\lfloor \frac{n}{2}\rfloor$个；
$\cdots \cdots$
对于范围$[1,n]$中是 n 的倍数的个数为 $\lfloor \frac{n}{n}\rfloor$个；

那么根据该式子我们可以将 $g(n)$ 的定义修改为:
$$g(n)=1^2\times \lfloor \frac{n}{1}\rfloor +2^2\times \lfloor \frac{n}{2}\rfloor +3^2\times \lfloor \frac{n}{3}\rfloor +\cdots \cdots +n^2\times \lfloor \frac{n}{n}\rfloor =\sum _{i=1}^n(i^2\times \lfloor \frac{n}{i}\rfloor )$$

如果按照上述式子计算的话，时间复杂度为$O(n)$，而 $n$ 最大为1e9，说明我们需要优化。仔细观察式子 $\lfloor \frac{n}{i}\rfloor$ 是一个模板的数论分块的式子，它可以帮助我们将求和的复杂度降低到$O(\sqrt{n})$。简略而言就是我们可以将区间$[1,n]$分成若干块区间 $[l,r]$，使得满足 $\lfloor \frac{n}{l}\rfloor =\lfloor \frac{n}{l+1}\rfloor =\lfloor \frac{n}{l+2}\rfloor =\cdots \cdots =\lfloor \frac{n}{r}\rfloor$。

例如$\lfloor \frac{12}{7}\rfloor =\lfloor \frac{12}{8}\rfloor =\lfloor \frac{12}{9}\rfloor =\cdots \cdots =\lfloor \frac{12}{12}\rfloor =1$，那么该区间的求和根据结合律我们可以进行如下操作：

$\lfloor \frac{12}{7}\rfloor \times 7^2+\lfloor \frac{12}{8}\rfloor \times 8^2+\lfloor \frac{12}{9}\rfloor \times 9^2+\cdots \cdots +\lfloor \frac{12}{12}\rfloor \times 12^2=(7^2+8^2+\cdots \cdots +12^2)\times \lfloor \frac{12}{7}\rfloor$

对于分成的任意块状区间我们都可以进行上述转换。不了解数论分块的请自行学习。

此时问题将转化为，对于任意区间 $[l,r]$ ，如何求出 $l^2+(l+1{)}^2+\cdots \cdots +r^2$。
这其实是有一个平方数前缀和公式的: $$\sum _{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}$$

证明见： 平方数前缀和公式

如果要求任意区间的$[l,r]$的平方和，那么只要类似前缀和思想用 $s[r]-s[l-1]$即可。在计算答案时，我们只需要保留记录一下$[1,l-1]$的平方前缀和就好，代码中用ans变量记录。再通过公式计算$[1,r]$的平方前缀和。这里需要注意的是公式中涉及了除法，而且题目还需要进行取模，所以我们需要使用逆元，否则会出现精度问题，这里先提前计算出了6在1e9+7下的逆元为166666668。不了解逆元的请自行学习。

至此，我们可以不断累积计算每个块状区间的答案，时间复杂度为$O(\sqrt{n})$。具体实现见代码细节

3.Ac_cdoe

#include
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;

LL n;
LL ans = 0, sum = 0;
// 储存结果
LL res = 0;
int inv6 = 166666668; //6在1e9+7下的逆元
//数论分块
void H() {
	LL l = 1, r;       // 块左端点与右端点
	while (l <= n) {
		r = n / (n / l);  // 计算当前块的右端点
		ans = sum;
		sum = r * (r + 1) % mod * (2 * r + 1) % mod * inv6 % mod;
		LL v = (sum - ans + mod) % mod;//求出区间[l,r]的平方和
		res = (res + (n / l) % mod * v % mod) % mod;
		l = r + 1;  // 左端点移到下一块
	}
}
void solve()
{
	cin >> n;
	H();
	cout << res << '\n';
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	while (t--)
	{
		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
42
43
44
45
46
47