出题人题解 | #因数个数和#

原题解链接：https://ac.nowcoder.com/discuss/149978

首先把因数个数和转化成倍数个数和，即 ${\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor \backslash sum\_\{i=1\}^\{n\}\backslash left\backslash lfloor\backslash frac\{n\}\{i\}\backslash right\backslash rfloor$

方法1:

利用 $\lfloor \frac{n}{i}\rfloor \backslash left\backslash lfloor\backslash frac\{n\}\{i\}\backslash right\backslash rfloor$ 只有 $O(\sqrt{n})O(\backslash sqrt\{n\})$ 种枚举计算。

方法2:

所求即 ${\sum }_{x,y\ge 1}[x\times y\le n]\backslash sum\_\{x,\; y\; \backslash geq\; 1\}[x\; \backslash times\; y\; \backslash leq\; n]$

考虑计算 ${\sum }_{y>x\ge 1}[x\times y\le n]\backslash sum\_\{y>x\; \backslash geq\; 1\}[x\; \backslash times\; y\; \backslash leq\; n]$ ，乘2再加上 $x=yx=y$ 的情况就是答案了。

而这个东西可以枚举 $xx$ 计算.

两个方法时间复杂度都是 $O(\sqrt{n})O(\backslash sqrt\{n\})$ 。

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

typedef long long s64;

int main()
{
	int tt;
	cin>>tt;
	while(tt--)
	{
		int n;
		cin>>n;
		s64 ans=0;
		for(int x=1;x*x<=n;++x)ans+=(n/x-x)*2+1;
		cout<<ans<<endl;
	}
}