整数分块可以以log(n)的时间复杂度内求出${\sum_{i=1}^n\lfloor n/i \rfloor}$

小G的约数

image-20210227160754599

解法

单纯求F(n)O(n)求出，现在求$\sum{i=1}^nF_i$，可以换种思路，从个体对整体的贡献下手，对于每一个约数求有这个约数的所有数数量，显然是n/i个，然后乘上i，那么问题就转化为了${\sum{i=1}^n\lfloor n/i \rfloor*i}$，很明显的整数分块模板，什么是整数分块，考虑n=10的时候n/i的表

i: 1 2 3 4 5 6 7 8 9 10

n/i: 10 5 3 2 2 1 1 1 1 1

发现数字呈从大到小块状分布，只要知道了一个块的左端和右端就能直接算出这个块的n/i的和，这里有一个结论：$N/i==N/i’时，i’的最大值：N/(N/i)$,i’也就是右端点，因此可以枚举每一段区间，n/i的所有数字中不同数字的数量不会超过2*sqrt(n)个，因此时复就是sqrt(n)

整数分块函数

1
2
3
4
5
6
7
8
9
ll get(ll x){
	ll ret=0;
    for(ll i=1;i<=x;i++){
        ll r=x/(x/i);
        ret+=x/i*(r-i+1);
	    i=r;  //把指针移到右端点的下一个位置，这里移到右端点是因为i++
    }
    return ret;
}

ACCODE

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
#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+100;
const double pi=acos(-1);
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const int eps=1e-4;
ll get(ll x){
	ll ret=0;
	for(int i=1;i<=x;i++){
		ll r=x/(x/i);
		ret+=(r-i+1)*(x/i)*(i+r)/2;  //这里要乘以等差数组前缀和
		i=r;
	}
	return ret;
}
int main(){
	ios;
	ll n;
	cin>>n;
	cout<<get(get(n))<<'\n';
	return 0;
}