GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

A26401. $星星的个数$

填空题较难

知识点

因数个数约数枚举数学建模时间复杂度优化

题目描述

星星的个数 题目描述 你每天都会收集不同数量的星星贴纸。当收集到第 k 天时 (1\leqk\leqn)，他当天获得的贴纸数量是 k 张，而每张贴纸上印着的星星数量等于 k 这个数字的因数个数（比如数字6有4个因数：1,2,3,6，就印4颗星星）。请计算你这 n 天收集到的星星总数。 输入格式 输入一个整数 n。 输出格式 共一行，这 n 天收集到的星星总数。 输入样例#1 4 输出样例#1 23 输入样例#2 100 输出样例#2 26879 输入样例#3 10000000 输出样例#3 838627288460105 数据范围 1 \leq N \leq 107 样例1说明 1 \times 1 + 2 \times 2 + 3 \times 2 + 4 \times 3 =23

参考答案

#include<iostream>
using namespace std;
int main()
{
    long long n;
    cin >> n;
    long long sum = 0;
    for (int d = 1; d <= n; ++d) {
        long long k = n / d;
        sum += d * (k + 1) * k / 2;
    }
    cout << sum << "\n";
    return 0;
}

上一题下一题