求前 $n$ 个数因数和的三种方法。

$sol\ 1:$ 纯暴力，对每个数，遍历 $1\sim\sqrt{i}$ 时间复杂度: $O(n^{\frac{3}{2}})$

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
int main(){
    int n,ans=0,j;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(j=1;j*j<=i;j++)
            if(i%j==0) ans+=(j+i/j);
        j--;
        if(j*j==i) ans-=j;
        }
    printf("%d\n",ans);
    return 0;
}

$sol\ 2:$ 考虑每个因数对答案的贡献，显然对1有 $n$ 次贡献， $2$ 有 $\lfloor\dfrac{n}{2}\rfloor$ 次贡献，依次类推，时间复杂度： $O(n)$

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
int main(){
    int n,ans=0; 
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        ans+=i*(n/i);
    printf("%d\n",ans);
    return 0;
}

$sol\ 3:$

$\sum\limits_{i=1}^n\sigma(i)=\sum\limits_{i=1}^ni\times\lfloor\dfrac{n}{i}\rfloor$

因为 $i\leq\sqrt{n}$ 时，对应 $\sqrt{n}$ 个 $\lfloor\dfrac{n}{i}\rfloor$ .同样当 $i>\sqrt{n}$ ,对应 $\sqrt{n}$ 个 $\lfloor\dfrac{n}{i}\rfloor$ 。

所以可以在 $i\in[1,\sqrt{n}]$ 中同时对 $i$ 和 $\lfloor\dfrac{n}{i}\rfloor$ 进行计算贡献。

显然对于固定左边的 $i$ ，贡献为 $i\times\lfloor\dfrac{n}{i}\rfloor$ .

而对于固定右边的 $\lfloor\dfrac{n}{i}\rfloor$ .这里的 $\lfloor\dfrac{n}{i}\rfloor$ 也从 $[1,\sqrt{n}]$ 开始遍历，这里的 $\lfloor\dfrac{n}{i}\rfloor$ 也就是程序里的 $i$ 。因为这样可以避免算重，这样算的贡献的是左边的所有的大于 $\sqrt{n}$ 的 $i$ 的贡献。这样大于 $\sqrt{n}$ 的 $i$ 产生的贡献加上小于等于 $\sqrt{n}$ 的 $i$ 产生的贡献就等于答案的贡献，即 $ans_{(i\leq\sqrt{n})}+ans_{(i>\sqrt{n})}=ans$ 。注意最后需要去重一下，因为可能存在 $i=\lfloor\dfrac{n}{i}\rfloor$ 的情况。

这样时间复杂度就能到 $O(\sqrt{n})$ 了。

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll ans,n,i;
int main(){
    while(~scanf("%lld",&n)){
        ans=0,i=1;
        for(i=1;i*i<=n;i++){
             ans+=i*(n/i);
             ll r=n/i,l=n/(i+1)+1;
             ans+=(l+r)*(r-l+1)/2*i;//区间[l,r],[n/i]=i时 的贡献. 
        }
        i--;
        if(i==(n/i)) ans-=i*(n/i);//去重 
        printf("%lld\n",ans);
    }
    return 0;
}

求前n个数因数和的三种方法。

求前个数因数和的三种方法。

求前 $n$ 个数因数和的三种方法。