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

# 小 G 的约数

image-20210227160754599

# 解法

单纯求 F (n) O (n) 求出,现在求i=1nFi\sum_{i=1}^nF_i,可以换种思路,从个体对整体的贡献下手,对于每一个约数求有这个约数的所有数数量,显然是 n/i 个,然后乘上 i,那么问题就转化为了i=1nn/ii{\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)N/i==N/i'时,i'的最大值:N/(N/i),i' 也就是右端点,因此可以枚举每一段区间,n/i 的所有数字中不同数字的数量不会超过 2*sqrt (n) 个,因此时复就是 sqrt (n)

# 整数分块函数

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

#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;
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝