UVA11526

H(n)

我们要先明白一个道理，虽然 $i$ 有 $n$ 种取值，但是 $\dfrac{n}{i}$ 实际上只有 $O(\sqrt n)$ 的取值。

然而我不会证。

所以在没有任何想法基础的情况下这个结论包括即将讲的做法基本没有做出来的可能。

先引出来一个结论：

若 $j=\lfloor \dfrac{n}{i} \rfloor$，则 $j$ 是满足 $\lfloor \dfrac{n}{j}\rfloor \ge i$ 的最大值。

我不会严谨证明，但是我可以给一个直观的理解。

可以想象一个长度为 $n$ 的序列被长度为 $i$ 的序列逐个覆盖，最多覆盖 $j$ 个这样的序列就没法再覆盖了，因此必然就有长度为 $j$ 的序列在这个长度为 $n$ 的序列上可以覆盖 $i$ 段及以上（因为 $ij=ji$），至于能否再继续用长度为 $j$ 的序列覆盖剩余的段我们并不知道。

因此我们会有 $\lfloor \dfrac{n}{j}\rfloor\ge i$。

如何理解这个 $j$ 是最大的？

比如说我们取一个稍大一点的值 $j+1$，根据我们上面的条件，显然 $i(j+1)>n$，那用长度为 $j+1$ 的序列去覆盖这个长度为 $n$ 的序列必然是覆盖不到 $i$ 段的。

然后我们就可以利用这个结论导出来另一个结论：

若 $j=\lfloor \dfrac{n}{\lfloor \frac{n}{i}\rfloor}\rfloor$，则 $j$ 是满足 $\lfloor\dfrac{n}{j}\rfloor\ge \lfloor \dfrac{n}{i}\rfloor$ 的最大值。

更进一步地，我们可以知道 $\lfloor \dfrac{n}{j}\rfloor=\lfloor\dfrac{n}{i}\rfloor$（根据最大性，实在看不出来就反证，其实挺显然的）。

更进一步地，我们可以知道 $k=j+1$ 是满足 $\lfloor \dfrac{n}{k}\rfloor<\lfloor \dfrac{n}{i}\rfloor$ 的最小值。

重要结论：

所以根据这个结论我们得到一个区间 $[i,j]$ 内的函数值都是相同的，同理 $[j+1,\lfloor\dfrac{n}{\lfloor\frac{n}{j+1}\rfloor}\rfloor]$ 内的函数值也都是相同的，以此类推。

上面的解释记不记住都无所谓，这个结论一定牢记。

于是时间复杂度与这样区间的数量有关，根据上面结论我们可以知道是 $O(\sqrt n)$ 的。

但我还是不会证。

有大神能救救孩子吗？

找到了一个 证明（在第五个），可惜还没时间看（怎么写这么长？）。

然后发现 OI wiki 上的证明更为强大。

引理 1：

$$\lfloor\dfrac{a}{bc}\rfloor=\lfloor\dfrac{\lfloor\dfrac{a}{b}\rfloor}{c}\rfloor$$

证明：

易知 $\dfrac{a}{b}=\lfloor\dfrac{a}{b}\rfloor+r$，$(0\le r<1)$。

代入左边，原式等于 $\lfloor\dfrac{\lfloor\dfrac{a}{b}\rfloor}{c}+\dfrac{r}{c}\rfloor$。

很显然 $r$ 与 $\lfloor\dfrac{a}{b}\rfloor\bmod c$ 的和一定 $<c$。

所以原等式成立。

引理 2：

$$\forall n \in N^*,\operatorname{card}({\lfloor\dfrac{n}{d}\rfloor\mid d\in N^*,d\le n})\le \lfloor2\sqrt{n}\rfloor$$

证明：

对于 $d\le \lfloor\sqrt{n}\rfloor$，$\lfloor\dfrac{n}{d}\rfloor$ 有 $\sqrt{n}$ 种取值；

对于 $d>\lfloor\sqrt{n}\rfloor$，很显然 $\lfloor\dfrac{n}{d}\rfloor\le \lfloor\sqrt{n}\rfloor$，于是也只有 $\lfloor\sqrt{n}\rfloor$ 种取值。

证毕了。

现在开始推广基本的数论分块。

要求：

$$\sum_{i=1}^n f(i)\lfloor\dfrac{n}{i}\rfloor$$

先将 $f(i)$ 的前缀和记作 $s(i)=\sum_{j=1}^i f(i)$。

每次将数值相同的块合并起来乘上这一段的和即可。

下面将数论分块拓展到多维。

其实就是把边界换一下，取个 $\min$ 即可。然后这东西显然还是 $O(k\sqrt{n})$ 的（其中 $k$ 是维数）。

然后我再拓展一下这题的结论。

我们所求的函数 $H(n)$ 是：

$$H(n)=\sum_{i=1}^{n}\lfloor\dfrac{n}{i}\rfloor=\sum_{i=1}^{n}\sigma_0(i)$$

证明的话把后面的东西写成卷积形式，然后交换一下求和顺序就好了。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

ll T,n,ans;

inline ll read() {
	ll ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
	return ret*f;
}

inline void write(ll x) {
	static char buf[22];static ll len=-1;
	if(x>=0) {
		do{buf[++len]=x%10+48;x/=10;}while(x);
	}
	else {
		putchar('-');
		do{buf[++len]=-(x%10)+48;x/=10;}while(x);
	}
	while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
	write(x);putchar('\n');
}

int main() {

	T=read();

	while(T--) {
		n=read();ans=0;
		for(ll i=1,j;i<=n;i=j+1) {
			j=n/(n/i);ans+=(j-i+1)*(n/i);
		}
		writeln(ans);
	}
	
	return 0;
}