洛谷 P2424 约数和

题目链接

思路 && 代码

数论分块

算是数论分块的模板题了吧

20分做法

纯暴力，直接枚举，然后每个数 $O(\sqrt{n})$ 判断，时间复杂度$O(n\sqrt{n})$

需要注意不要闷着头一直枚举到$\sqrt{n}$，如果$n$的约数$i$的平方恰好等于$n$，只加一个就足够了

int x, y, ans;

signed main() {
	x = read(), y = read();
	for (int i = x; i <= y; i++) {
		for (int j = 1; j <= sqrt(i); j++) {
			if (!(i % j)) {
				if (j * j == i) ans += j;
				else ans += j + (i / j);
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

60分做法

也是一种暴力 思路是转枚举约数为枚举倍数

容易得出一个数$i$ 在$n$中一共有 $\lfloor \frac{n}{i}\rfloor$ 个$i$的倍数，那么$i$在$n$中的贡献为 $\lfloor \frac{n}{i}\rfloor \ast i$
所以我们可以先求出$1\sim y$中每个$i$的贡献，然后再减去$1\sim x-1$中每个$i$的贡献
答案就是$\sum _{i=1}^y\lfloor \frac{y}{i}\rfloor \ast i-\sum _{i=1}^{x-1}\lfloor \frac{x-1}{i}\rfloor \ast i$

时间复杂度$O(y)$

int x, y, ans1, ans2;

signed main() {
	x = read(), y = read();
	for (int i = 1; i <= y; i++) ans1 += (y / i) * i;
	for (int i = 1; i <= x - 1; i++) ans2 += ((x - 1) / i) * i;
	cout << ans1 - ans2 << '\n';
	return 0;
}

正解

我们来看一下$\lfloor \frac{n}{i}\rfloor (1\le i\le n)$的取值有什么规律，假设$n$为$18$，那么每个$\lfloor \frac{n}{i}\rfloor$的值分别为

$18,9,6,4,3,3,2,2,2,1,1,1,1,1,1,1,1,1$

很显然，有很多$\lfloor \frac{n}{i}\rfloor$的值是一样的，所以我们可以用数论分块来做

关于数论分块，如果不会可以去看Luckyblock的博客，内容详实，证明详细，讲的非常棒（实名墙裂推荐）

如果你看完了这篇博客，那么~~（我觉得我就没必要讲了）~~我们就继续讲

显然，我们现在的任务就是求出$\lfloor \frac{n}{i}\rfloor$值相同的区间$l,r$，初始化$l$为$1$，每次枚举新的值得时候$l=r+1$,那么问题来了，$r$怎么求呢？

其实并不难，上面的博客里也讲证明了，如果让我证明也就是把他的博客里的证明搬过来，就是$r=n/(n/l)$

$l$和$r$都明白了，那么答案每次怎么累加呢？

应该是$ans+=$此时的约数 * 这个区间的约数个数和

约数就是$n/l$，因为$l$就是当前数列的下标，所以$n/l$就是约数，约数个数和也比较显然，就是$\sum _{i=l}^{r}i$，利用等差数列求和公式，就可以$O(1)$求出这个式子的答案

等差数列求和公式的两种写法

$a_1$是首项，$a_n$是末项，$d$是公差，$S$是等差数列的和，那么写法就有以下两种

1. $S=n{a}_1+\frac{n(n-1)}{2}d$
2. $S=n(a_1+a_n)/2$

最后的答案就是算出的$1\sim y$的贡献减去$1\sim x-1$的贡献，然后这道题就做完啦~

时间复杂度$O(\sqrt{n})$

/*
Author:loceaner
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int A = 1e7 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
	char c = getchar();
	int x = 0, f = 1;
	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return x * f;
}

int x, y;

inline int sum(int l, int r) {
//	return (r - l + 1) * (l + r) / 2;
	return 1ll * ((r - l + 1) * l) + 1ll * ((r - l + 1) * (r - l) / 2);
}

inline int solve(int n) {
	int ans = 0;
	for (int l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l);
		ans += (n / l) * sum(l, r);
	}
	return ans;
}

signed main() {
	x = read(), y = read();
	cout << solve(y) - solve(x - 1) << '\n';
	return 0;
}