文章目录
  1. 1. 约数求和
    1. 1.1. 暴力算法
    2. 1.2. 稍微有点脑子的算法
    3. 1.3. 改进的算法
    4. 1.4. 有趣的做法
  2. 2. 拓展

引言:看如何在大腿的指导下把复杂度从O(n2)O(n^2)降低到O(n)O(\sqrt n)


约数求和

来自:复旦大学研究生机试题目解析(2016-2018)

我感觉是个非常有趣的题。

原po太过暴力了,复杂度是O(n2)O(n^2)的。

暴力算法

下面给个暴力的:

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
#include <iostream>
#include <math.h>
using namespace std;

int countysh(int a) {
int sum = 0;
int t=sqrt(a);
for (int i = 1; i <= t; i++) {
if (a%i == 0){
if(i!=a/i){
sum += i + a/i;
}else{
sum += i;
}
}

}
return sum;
}

int main() {
int input, sum = 1;//1的约数为1;
cin >> input;
for (int i = 2; i <= input; i++) {
sum += countysh(i);
}
cout << sum << endl;
return 0;
}

这个复杂度是O(nn)O(n\sqrt n)的,基本上都能想到。

稍微有点脑子的算法

可以用筛法的思想,复杂度O(nlogn)O(nlogn),但这个做法没有办法handle大n,因为数组开不了那么大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll arr[10000010];
int n;
int main() {
scanf("%d",&n);
arr[1]=1;
for(int i=2;i<=n;i++){
++arr[i];//1给的贡献
for(int j=i;j<=n;j+=i){
arr[j]+=i;
}
}
ll sum=0;
for(int i=1;i<=n;i++){
sum+=arr[i];
}
printf("%lld\n",sum);
return 0;
}

改进的算法

上述算法必须开数组,但实际上不需要。

1会贡献n,2会贡献2(n/2)2*(n/2),3会贡献3(n/3)3*(n/3),以此类推。

复杂度O(n)O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
int main() {
scanf("%d",&n);
ll sum=0;
for(int i=1;i<=n;i++){
sum+=i*(n/i);
}
printf("%lld\n",sum);
return 0;
}

有趣的做法

实际上可以看出in/ii*\lfloor{n/i}\rfloor可以用整除分块做,复杂度O(n)O(\sqrt n)

大意是,ii在一定范围变化时,n/i\lfloor n/i \rfloor是一个定值,称范围为左界到右界。

枚举每个范围的右界的方法是:计算右界等于nn/i0\frac {n} {\lfloor n/i_0 \rfloor},称n/i\lfloor n/i \rfloorii[i0,nn/i0][i_0,\frac {n} {\lfloor n/i_0 \rfloor}]范围内是一个定值。显然,nn/i0+1\frac {n} {\lfloor n/i_0 \rfloor}+1为下一个范围的左界。

那么上述问题转换为分块的等差数列求和,当ii[i0,nn/i0][i_0,\frac {n} {\lfloor n/i_0 \rfloor}]时,计算

i=i0n/n/iin/i0\sum_{i=i_0}^{n/\lfloor n/i \rfloor} i*\lfloor n/i_0 \rfloor

用等差数列求和公式即可转换为:

(nn/i0i0+1)(i0+nn/i0)2n/i0\frac{(\frac {n} {\lfloor n/i_0 \rfloor}-i_0+1)(i_0+\frac {n} {\lfloor n/i_0 \rfloor})}{2}*\lfloor n/i_0 \rfloor

上述公式计算ii[i0,nn/i0][i_0,\frac {n} {\lfloor n/i_0 \rfloor}]范围的值,最后求和所有的块即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
int main() {
scanf("%d",&n);
ll sum=0;
int i=1;
int k,r;
while(i<=n){
k=n/i;
r=n/k;
sum+=(r-i+1)*(i+r)/2*k;
i=r+1;
}
printf("%lld\n",sum);
return 0;
}

拓展

https://blog.csdn.net/controlbear/article/details/77527115?tdsourcetag=s_pcqq_aiomsg

算术基本定理:任何大于1的自然数,都可以表示成有限个素数(可以重复)的乘积,并且如果不计次序的话,表法是唯一的。

根据算数基本定理,我们可以将任意的数拆成小于它的素数的乘积,记pip_i为素数。

a=p1a1p2a2...pkaka=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k}

某个数的约数(因数)和:

sd(N)=(1+p1+p12+...+p1a1)(1+p2+p22+...+p2a2)...(1+pk+pk2+...+pkak)sd(N)=(1+p_1+p_1^2+...+p_1^{a_1})(1+p_2+p_2^2+...+p_2^{a_2})...(1+p_k+p_k^2+...+p_k^{a_k})

某个数的约数(因数)个数:

d(N)=(1+a1)(1+a2)...(1+ak)d(N)=(1+a_1)(1+a_2)...(1+a_k)

在上述csdn博客中,提供了一种“用线性筛打表出 1 到 N 的约数和”的方法,用在本题为O(n)的复杂度。

文章目录
  1. 1. 约数求和
    1. 1.1. 暴力算法
    2. 1.2. 稍微有点脑子的算法
    3. 1.3. 改进的算法
    4. 1.4. 有趣的做法
  2. 2. 拓展