求 1~N 每个数的约数个数之和 题解

题意简述：

$$ans = \sum_{i = 1}^{n} σ(i)$$

写对应不同范围数据的解法

1.O(n)

$$\sum_{i = 1}^{n} σ(i)$$ $$=\sum_{i = 1}^{n} \sum_{j=1}^{n} [j \mid i]$$ $$=\sum_{j = 1}^{n} \sum_{i=1}^{n} [j \mid i]$$ $$=\sum_{j = 1}^{n} \lfloor n/j \rfloor$$

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
signed main(){
	cin>>n;
	for(int i = 1;i<=n;i++)ans+=(n/i);
	cout<<ans<<'\n';
	return 0;
}

2.O(n/2)

和上面的1.0版本差不多...

发现对于一个数k，它的因子只能 < n/2上取整(1*k这一组除外)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
signed main(){
	cin>>n; 
	for(int i = 1;i<=n/2;i++)ans+=n/i;
	ans+=(n-n/2);//可以举个奇数的例子 这是上取整 
	cout<<ans<<'\n';
	return 0;
}

3.O(√n)

一种是分块：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
signed main(){
	cin>>n;
	for(int i=1,j;i<=n;i=j+1){
		j=min(n/(n/i),n);
		ans+=(n/i)*(j-i+1);
	}
	cout<<ans<<'\n';
	return 0;
} 

这个东西常数大，过不了后四个点。

---

还有一种是正解：

让我们从1.0版本的式子继续往下推喽~我们刚才到这：

$$ans=\sum_{j = 1}^{n} \lfloor n/j \rfloor$$

为了方便表示，我把这个式子中的j换成i。则有：

$$ans=\sum_{i = 1}^{n} \lfloor n/i \rfloor$$ $$=\sum_{i = 1}^{n} \sum_{j = 1}^{n} [i*j<=n]$$ $$=\sum_{i = 1}^{\sqrt{n}} \sum_{j = 1}^{n/i} 1 + \sum_{j = 1}^{\sqrt{n}} \sum_{i = 1}^{n/j}1 - (?) $$

本人过蒻，在观看Amy29大佬的优化版代码后才继续推出（?）是什么...

$$（?）= \sum_{i = 1}^{\sqrt{n}} \sum_{j = 1}^{\sqrt{n}} 1 $$

Move on!

$$ans=\sum_{i = 1}^{\sqrt{n}} \sum_{j = 1}^{n/i} 1 + \sum_{j = 1}^{\sqrt{n}} \sum_{i = 1}^{n/j}1 - \sum_{i = 1}^{\sqrt{n}} \sum_{j = 1}^{\sqrt{n}} 1 $$$$=2*\sum_{i = 1}^{\sqrt{n}} \lfloor n/i \rfloor - (\lfloor \sqrt{n} \rfloor)^2 $$

这不清晰!?! 这可太棒了！！！

这里还有一个需要注意的地方，尤其是针对（?）的处理，就是一定要定义一个sq=√n。Cuz注意到上式中涉及到√n的部分我们需要下取整，恰好c++对于用int存一个带精度的数的时候就是下取整。

然后剩下的前半部分式子就不用说了，和1.0版本一模一样，只是循环从1~√n。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,sq,ans;
signed main(){
	cin>>n;
	sq=sqrt(n);
	for(int i=1;i<=sq;i++)ans+=(n/i); 
	ans*=2;
	ans-=sq*sq;
	cout<<ans<<'\n';
	return 0;
}

（激动的心颤抖的手 请对着式子看代码 简直太清晰了!

这是一篇记录了思考过程的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;
}

这里放一个科技

首先众所不周知，有一种二叉搜索树是 Stern Bocot Tree

然后相关内容可以移步这里 https://oi-wiki.org/math/number-theory/stern-brocot/

我觉得维基百科说的挺好的。

然后如果您觉得我写得太弱了，根本不本质，也可以移步这里 看里面第一篇题解

首先有一个非常 navie 的做法叫做，我考虑枚举根号以内的数，然后计算 $2\sum n/i$ 然后因为中间有 $B*B$ 重复计算过了，把它们减去就好了

那么好，步入正题

我们考虑这个东西的几何意义

放张图

我们发现我们要求的无非就是紫色区域内的整点个数（不算坐标轴）

于是我们考虑积分拟合这个函数，（积分精度绝对爆炸）

所以我们要二分往后走的向量。

其实所谓的二分本质上就是对$L$ 向量和 $R$ 向量求和。

然后发现 $L+R$ 向量的斜率恰好在它们之间。

于是我们就可以二分了。

我们的$chk$是判断走完这一步向量会不会走到紫色区域里面。

如果走不进去，把 $R$ 赋值成$mid$

如果走的进去，我们要分类讨论一下：

如果我们走完这一步向量所在位置的函数导数不大于向量斜率，就说明我们无论怎么二分，都一定会走到函数里面。

如图，我们发现当前的$L$ 向量无论加多少 $R$ 向量，都不可能走出去了。

反之，就继续进行二分。

然后如果我们直接每一次走的时候都这样二分非常傻，注意到我们的向量是单调递增的，我们每一次把走不进去的向量丢到单调栈里面，下一次我们找相邻的两个向量，且$L$ 恰好走得进去，$R$ 恰好走不进去，接着进行二分。

对于那些斜率比$L$还大，那我们就可以丢掉了，因为我们以后一定不会用到这些向量。

然后直接这么做，根据论文复杂度是错的，所以我们对于 $n^{\frac{1}{3}}$ 之内的直接暴力，否则按照上述方式走。

首先我们枚举一个 $n$ 的因数个数就是枚举到 $\sqrt{n}$ ，然后我们对于这道题也考虑这样做

首先我们枚举每一个 $\sqrt{n}$ 的数，然后对于每一个数 $i$ ，我们考虑 $i$ 出现过的次数为 $\frac{n}{i}$ ，然后我们最后答案后 $\times 2$

但是我们发现会有一个问题就是说我们可能会算重，算重的个数为 $\sqrt{n} \times \sqrt{n}$

signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	T=reads();
	while(T--){
		clr();
		n=reads(),m=sqrt(n);
		for(int i=1;i<=m;i++) ans+=n/i;
		ans*=2;
		ans-=m*m;
		printf("%lld\n",ans);
	}
	return 0;
}

刚看到题目可以想到O(N)做法

答案就是$\sum_{i=1}^{n}\frac{n}{i}$

然后可以得到30pts

然后我们观察n/i,发现一共有$\sqrt{n}$段，然后我们暴力枚举每个段，然后复杂度是$O(2\sqrt{n})$

我不知道为什么，这个做法可以拿100pts

最后就是正解

我们考虑$\sqrt{n}$内可以对多少数产生贡献，即$\sqrt{n}$内作为约数的个数，记为S，那么对于大于$\sqrt{n}$的所没有用过的约数，也为S，但是会有减多的，所以我们要减去在$\sqrt{n}$内重复出现的即$\sqrt{n}*\sqrt{n}$

eg:1到100内2与3共同组成的6被多算了一次

这个的复杂度为$O(\sqrt{n})$

code1

void compute(){
	long long ans = 0;
	for(long long i = 1;i <= n; i++){
		ans += n / i;
	}
	W(ans);
}

code2

void compute(){
	long long ans = 0;
	for(long long i = 1;i * i <= n; i++){
		ans += n / i;
		if(n / i > i)
		ans += (n / i - n / (i + 1)) * i;
	}
	W(ans);
}

code3

void compute(){
	long long ans = 0;
	long long q = sqrt(n);
	for(long long i = 1;i <= q; i++){
		ans += n / i;
	}
	ans *= 2;
	ans -= q * q;
	W(ans);
}