A New Function(除法分块)题意：思路：

63 阅读 0 评论 42 点赞

我是靠谱客的博主犹豫热狗，最近开发中收集的这篇文章主要介绍A New Function(除法分块)题意：思路：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门

题意：

设f(i)为i除了1和i之外的约数的和，求 $sum_1^if(i)$ 。

思路：

对于n来说，1~n中是i的倍数的个数有n/i个，利用这个可以很轻松的计算出约数i的贡献，但枚举每一个约数在时间复杂度上肯定过不去，于是想到除法分块，对于数n的每一个除法分块 $l_i,r_i]$ ， $n/l_i-1$ 就为这一段区间中的每一个数的贡献次数(不计算1和本身)，用这一段区间的和乘上贡献次数即可得出这段区间的总贡献。

#include<bits/stdc++.h>
using namespace std;
#define ll long long



int main()
{
	int t;
	cin>>t;
	for(int i = 1; i <= t; i++)
	{
		ll ans = 0;
		ll n;
		cin>>n;
		ll l = 1;
		while(l < n)
		{
			ans += (l+n/(n/l))*(n/(n/l)-l+1)/2*(n/l-1);
			l = n/(n/l)+1;
		}
		if(n == 0)cout<<"Case "<<i<<": "<<0<<endl;
		else
		cout<<"Case "<<i<<": "<<ans-n+1<<endl;
		
	}
	
}