P2424 约数和

题目背景

Smart最近沉迷于对约数的研究中。

题目描述

对于一个数X，函数f(X)表示X所有约数的和。例如：f(6)=1+2+3+6=12。对于一个X，Smart可以很快的算出f(X)。现在的问题是，给定两个正整数X,Y(X<Y)，Smart希望尽快地算出f(X)+f(X+1)+……+f(Y)的值，你能帮助Smart算出这个值吗？

输入输出格式

输入格式：

输入文件仅一行，两个正整数X和Y（X<Y），表示需要计算f(X)+f(X+1)+……+f(Y)。

输出格式：

输出只有一行，为f(X)+f(X+1)+……+f(Y)的值。

**错误日志：传导参数的时候没有用 $LL$ **

Solution

首先利用前缀和的思想，我们只要能求出 $1 - n$ 的约数和的和，就能求出一段区间的约数和的和

那么如何快速求出从 $1$ 开始约数和的和呢

很朴素大暴力万岁！的算法是 $O(\sqrt{n})$ 计算每个数的约数进行累加，然后慢到爆炸

我们可以换种思维，考虑枚举约数

显然对于一个约数 $d$ ，在 $1 - n$ 中出现过 $\lfloor \frac{n}{d}\rfloor$ 次，所以这一约数贡献的答案为 $\lfloor \frac{n}{d}\rfloor * d$

所以 $1-n$ 总因数和为 $$\sum_{i = 1}^{n}\lfloor \frac{n}{i}\rfloor * i$$

这样依然需要枚举 $1-n$ 这 $n$ 个因数， $O(n)$ 依然达不到复杂度要求

其实看到 $\lfloor \frac{n}{d}\rfloor$ 时我们很兴奋：除法分块！

（之前学的除法分块是假的。。现在补个真的）

比如说当 $n = 12$ 时，我们分别计算 $\lfloor\frac{n}{i}\rfloor\ (1 <= i <= n)$ 可以得到以下结果：

$12,6,4,3,2,2,1,1,1,1,1,1$

注意有部分连续的向下取整值是一样的！除法分块就是利用打表找规律来求出每个区间的左右端点以达到进行快速运算的目的

左端点很容易求解，即为上一个右端点 +1（初始值为1）

右端点通过打表找规律可知： $r = n / (n / l)$

然后就先配一个除法分块的板子

for(LL l = 1,r;l <= n;l = r + 1){

		r = n / (n / l);

		//向下取整的答案为 (n / l)

		//区间长度为(r - 1 +1)

		//这里操作

		}

于是我们得到的这一个区间的每个因数的数量都是 $(n / l)$

这些因数有哪些呢？当然就是 $l - r$ 里头这些啦

然后很显然这些因数构成了一个等差数列，单对于这一区间因数来说，其和为 $(l + r) * (r - l + 1) / 2$

每个因数有 $(n / l)$ 个，所以这一区间对答案的贡献为 $(n / l) * (l + r) * (r - l + 1) / 2$

于是有核心代码：

LL get_sum(LL n){

	LL ans = 0;

	for(LL l = 1,r;l <= n;l = r + 1){

		r = n / (n / l);

		ans += (n / l) * (l + r) * (r - l + 1) / 2;

		}

	return ans;

	}

前缀和一减就完事了，复杂度 $O(\sqrt{n})$

最后感谢学长提供好题，真的搞懂了除法分块（ヾ(^▽*)))）

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

typedef long long LL;

using namespace std;

LL RD(){

    LL out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

LL x, y;

LL get_sum(LL n){

	LL ans = 0;

	for(LL l = 1,r;l <= n;l = r + 1){

		r = n / (n / l);

		ans += (n / l) * (l + r) * (r - l + 1) / 2;

		}

	return ans;

	}

int main(){

	x = RD(), y = RD();

	printf("%lld\n", get_sum(y) - get_sum(x - 1));

	return 0;

	}

巴特西

P2424 约数和 && 真丶除法分块

P2424 约数和

Solution

Code

最新文章

热门文章