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

纯暴力，对每个数，遍历 时间复杂度:

#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;
}

考虑每个因数对答案的贡献，显然对1有次贡献，有次贡献，依次类推，时间复杂度：

#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;
}

因为时，对应个 .同样当,对应个。

所以可以在中同时对和进行计算贡献。

显然对于固定左边的，贡献为.

而对于固定右边的.这里的也从开始遍历，这里的也就是程序里的。因为这样可以避免算重，这样算的贡献的是左边的所有的大于的的贡献。这样大于的产生的贡献加上小于等于的产生的贡献就等于答案的贡献，即。注意最后需要去重一下，因为可能存在的情况。

这样时间复杂度就能到了。

#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;
}