这是一篇记录了思考过程的tj（大佬可直接跳到最后一步try4）

try1：

• 从1-n枚举每一个约数，将它对应的数+1，最后把所有数的约数个数加起来即可。复杂度O（NlnN）

const ll N = 1e7+10;
ll n;
ll a[N];
void work()
{
	cin>>n;
	for (ll i=1; i<=n; i++)
		for (ll j=1; j*i<=n; j++)
			a[i*j]++;
	for (ll i=1; i<=n; i++) a[i]+=a[i-1];
	cout<<a[n];
}

try2：

• 对于上一次的暴力，我们发现，对于每一个约数i，它的第二层循环会跑n/i次，即对答案产生的贡献为n/i，所以第二层循环可以省掉，改为ans+=n/i；

ll n, ans;
void work()
{
	cin>>n;
	for (ll i=1; i<=n; i++)
		ans += n/i;
	cout<<ans;
}

try3：

假设n=10，(i：1->10) n/i = 10 5 3 2 2 1 1 1 1 1;。我们发现，n/i=2出现了2次，n/i=1出现了5次，可以分块进行优化。

假设当前枚举到的i为块的开始：

• 当前块的贡献均为：k=n/i
• 块的结束：j=n/k
• 块的长度：j-i+1
• 对答案的贡献：ans+=k*(j-i+1)

ll n, k, j, ans;
void work()
{
	cin>>n;
	for (ll i=1; i<=n; ) {
		k = n/i;
		j = n/k;
		ans += k*(j-i+1);
		i = j+1;
	}
	cout<<ans;
}

try4：

怎么60分！还没结束吗？并没有。

我们重新回try1推

for (ll i=1; i<=n; i++)
	for (ll j=1; j<=n/i; j++)
		ans++;

优化这个暴力：

ll n, q, ans;
void work()
{
	cin>>n;
	q = sqrt(n);
	for (ll i=1; i<=q; i++)
		for (ll j=1; j<=n/i; j++)
			ans++;
	for (ll j=1; j<=q; j++)
		for (ll i=1; i<=n/i; i++)
			ans++;
	ans = ans-q*q;
	cout<<ans;
}

• 当i<=q时，j<=n
• 当i>=q时，j<=q

对于第二种情况，把j和i掉换位置，就和第一种情况相同了。

其实不完全相同，虽然1<=j<=q，但i没法从1到n/j（i>=q），所以要剪掉第二种情况中，1<=i<=q的贡献（即1<=j<=q且1<=i<=q的情况），ans-=q*q

ll n, q, ans;
void work()
{
	cin>>n;
	q = sqrt(n);
	for (ll i=1; i<=q; i++) ans+=n/i;
	ans = ans*2-q*q;
	cout<<ans;
}