solve1(n):
- 埃氏筛法: 使用埃氏筛法对1到n的数进行素数筛分，同时计算每个数的最大素因子和最小素因子幂。
- 约数和公式: 利用约数和公式，通过最大素因子和最小素因子幂来计算每个数的约数和。
- 累加: 将所有数的约数和相加，得到最终结果。
solve2(n):
- 枚举约数: 对于每个数i，枚举它的所有约数j，将i/j也作为约数，然后将i*j累加到答案中。
- 去重: 由于每个约数会被计算两次，因此最后需要将答案除以2。

算法复杂度：

solve1: 线性筛法的复杂度为O(n log logn)，约数和公式的计算复杂度为O(1)，因此总时间复杂度为O(nloglogn)。
solve2: 对于每个数i，枚举约数的复杂度为O(n)，因此总时间复杂度为O(n)。

/**************************************************************** 
 * Description: 2023CSP_S_R2
 * Author: Alex Li
 * Date: 2024-06-04 09:31:04
 * LastEditTime: 2024-09-12 22:46:55
****************************************************************/
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

long long solve1(int n) {
    vector<bool> p(n + 1, true);  //判断是否为素数，true为素数
    vector<long long> f(n + 1, 0), g(n + 1, 0);
    f[1] = 1;
    //埃氏筛法找素数  
    for (int i = 2; i * i <= n; i++) {
        if (p[i]) {
            vector<int> d;
            //在d里存i的幂次，如果i=2  d中就是2，4，8... 
            for (int k = i; k <= n; k *= i)d.push_back(k); 
            //把d中的数反转
            reverse(d.begin(), d.end());
            for (int k : d) { //遍历向量 d 中的每个元素 k
                for (int j = k; j <= n; j += k) {// 从 k 开始，步长为 k，遍历 j
                    if (p[j]) {// 如果 p[j] 为 true
                        p[j] = false; // 将 p[j] 设为 false，表示 j 不是素数
                        f[j] = i; //j的最小质因子i
                        g[j] = k; //最小质因子的最大幂次
                    }
                    
                }
               
            }
        }
    }
    //大于sqrt(n)的部分，如果是i质数，把相应的f和g数组填满
    for (int i = sqrt(n) + 1; i <= n; i++) {
        if (p[i]) {
            f[i] = i;
            g[i] = i;
        }
    }
    long long sum = 1; // 初始化总和为1（即f[1]）
    /*
    sum求所有数字i的约数和f[i]的和, 
    比如2的约数有1，2，之和是3，4的约数有1，2，4，约数和是7
    从2~10的约数和分别是3 4 7 6 12 8 15 13 18
    sum=1+f[2]+...f[n]=87
    */
    for (int i = 2; i <= n; i++) {
        f[i] = f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);
        sum += f[i];
    }
    return sum;
}
// 直接枚举法计算每个数的约数之和
long long solve2(int n) {
    long long sum = 0;
    // 对于每个数i，累加i的所有倍数
    for (int i = 1; i <= n; i++) {
        sum += i * (n / i);// i是n/i个数的约数
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    cout << solve1(n) << endl;
    cout << solve2(n) << endl;
    return 0;
}

Previous Topic

Back to Lesson

Next Topic