第十三届蓝桥杯Java省赛A组 H 题、C组 I 题，Python C 组 J 题—— 因数平分和 (AC)

电玩女神 2023-09-28 23:25 18阅读 0赞

#### 目录 ####

*  1. 因数平分和
 *   *  1.题目描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.数据范围
     *  7.原题链接
 *  2.解题思路
 *  3.Ac\_cdoe

## 1. 因数平分和 ##

### 1.题目描述 ###

记  f ( x ) f(x) f(x) 为  x x x 的所有因数的平方的和。例如:  f ( 12 ) = 1 2 + 2 2 + 3 2 + 4 2 + 6 2 + 1 2 2 f(12)=1^\{2\}+2^\{2\}+3^\{2\}+4^\{2\}+6^\{2\}+12^2 f(12)=12\+22\+32\+42\+62\+122

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

### 2.输入格式 ###

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

### 3.输出格式 ###

输出一个整数表示答案  g ( n ) g(n) g(n) 除以  1 0 9 + 7 10^\{9\}+7 109\+7 的余数。

### 4.样例输入 ###

100000

### 5.样例输出 ###

680584257

### 6.数据范围 ###

1 ≤ n ≤ 1 0 9 1\\leq n \\leq 10^\{9\} 1≤n≤109

### 7.原题链接 ###

[因数平方和][Link 1]

## 2.解题思路 ##

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

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

那么根据该式子我们可以将  g ( n ) g(n) g(n) 的定义修改为:  
 g ( n ) = 1 2 × ⌊ n 1 ⌋ + 2 2 × ⌊ n 2 ⌋ + 3 2 × ⌊ n 3 ⌋ + ⋯ ⋯ + n 2 × ⌊ n n ⌋ = ∑ i = 1 n ( i 2 × ⌊ n i ⌋ ) 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+n^2 \\times\\lfloor \\frac\{n\}\{n\} \\rfloor=\\sum\_\{i=1\}^\{n\}\{(i^\{2\} \\times\\lfloor \\frac\{n\}\{i\} \\rfloor)\} g(n)=12×⌊1n⌋\+22×⌊2n⌋\+32×⌊3n⌋\+⋯⋯\+n2×⌊nn⌋=i=1∑n(i2×⌊in⌋)

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

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

⌊ 12 7 ⌋ × 7 2 + ⌊ 12 8 ⌋ × 8 2 + ⌊ 12 9 ⌋ × 9 2 + ⋯ ⋯ + ⌊ 12 12 ⌋ × 1 2 2 = ( 7 2 + 8 2 + ⋯ ⋯ + 1 2 2 ) × ⌊ 12 7 ⌋ \\lfloor\\frac\{12\}\{7\} \\rfloor \\times7^2+\\lfloor\\frac\{12\}\{8\} \\rfloor \\times 8^2+\\lfloor\\frac\{12\}\{9\} \\rfloor \\times 9^2 +⋯ \\cdots+\\lfloor\\frac\{12\}\{12\} \\rfloor \\times 12^2 =(7^2+8^2+⋯ \\cdots+12^2)\\times \\lfloor\\frac\{12\}\{7\}\\rfloor ⌊712⌋×72\+⌊812⌋×82\+⌊912⌋×92\+⋯⋯\+⌊1212⌋×122=(72\+82\+⋯⋯\+122)×⌊712⌋

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

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

证明见： [平方数前缀和公式][Link 2]

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

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

## 3.Ac\_cdoe ##

#include<bits/stdc++.h>
    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;
    }

[Link 1]: https://www.lanqiao.cn/problems/2139/learning/
[Link 2]: https://www.cnblogs.com/olderciyuan/p/15567093.html