SP14138题解

Enoch006 · 2023-04-16 09:33:17 · 题解

题目大意：

给定 n，求 \sum_{i=1}^n\sum_{j|i} j 的值。

其实这个式子的意思就是求 1 到 n 所有数除去自己本身的因数的和。

题目思路：

第一种在每次输入时暴力枚举 1 到 n 所有数除去自己本身的因数的和。很明显，这样会超时。

既然每次都算一遍太浪费时间，我们可以预先处理每个数除去自己本身的因数有哪些接着相加，求他们的和只需要一个累加数组循环就行了。最后输入哪个数就输出这个累加数组这个数的值。

题目代码：

#include<bits/stdc++.h>
#define maxn 1005
#define maxm 1000005
using namespace std;
long long t,x,y,z,cnt,n,m,s[maxm],a[maxm];
int main(){
    cin>>n;
    for(int i=1;i<=1000000;i++){
        for(int j=2;j<=1000000/i;j++){
            a[i*j]+=i;
        }
    }
    for(int i=1;i<=1000000;i++){
        s[i]=s[i-1]+a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>x;
        cout<<s[x]<<endl;
    }
    return 0;
}