python/TangDou/AcWing/DP/Tree/求约数和的三重境界.md

求约数和的三重境界

一、先上结论

数据量/办法	暴力O(N^2)	普通筛法O(N\cdot logN)	欧拉筛法O(N)
n=1e5	13402ms	4ms	2ms
n=1e6	无法忍受，不能出结果	67ms	15ms

考虑到O(N^2)的复杂度，按C++一秒1e8的运算能力，1e6*1e6=1e12,应该是需要1e12 /1e8=1e4=10000秒，三个小时，去死吧！太垃圾了~

注意：

• 普通筛法:代码极短，性能足够，推荐使用
• 欧拉筛法：代码太长，性能优秀，不推荐使用

二、暴力法

//暴力大法 , 不包含自己
int bforce(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        if (n % i == 0)
            sum = sum + i;
    }
    return sum;
}

时间复杂度O(N^2)

三、普通筛法

 for (int i = 1; i <= n; i++)         // O(n)
    for (int j = 2; j <= n / i; j++) // 调和级数O(logn) = n + n / 2 + n / 3 + ... + n/n = lnn + c
        sum2[i * j] += i;

时间复杂度O(N\cdot logN)

四、线性筛法

原理解析

int primes[N], cnt; // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
int num[N];         // i的最小质因子构成的一个等比数列求和的结果
int sd[N];          //约数和
void get_primes(int n) {
    sd[1] = 1; // 1的约数和是1

    for (int i = 2; i <= n; i++) { //遍历　2~n,筛质数的同时，筛出每个数字的约数和
        if (!st[i]) {              //如果i是质数
            primes[cnt++] = i;     //记录i到质数数组中
            sd[i] = num[i] = 1 + i; //质数的约数和是1+自身
        }
        for (int j = 0; primes[j] * i <= n; j++) { 
            st[i * primes[j]] = true;              //记录primes[j]的整数倍(i倍)是合数

            if (i % primes[j]) { //如果i不包含primes[j]这个质数因子
                sd[i * primes[j]] = sd[i] * sd[primes[j]];
                num[i * primes[j]] = primes[j] + 1;
            } else { //如果i包含了primes[j]这个质数因子
                sd[i * primes[j]] = sd[i] / num[i] * (num[i] * primes[j] + 1);
                num[i * primes[j]] = num[i] * primes[j] + 1;
                break;
            }
        }
    }
}

五、附：测试对比的代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1e6 + 10;
int sum1[N], sum2[N], sd[N];
int n = 1e5;

//暴力大法 , 不包含自己
int bforce(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        if (n % i == 0)
            sum = sum + i;
    }
    return sum;
}

int primes[N], cnt; // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
int num[N];         // i的最小质因子构成的一个等比数列求和的结果
int sd[N];          //约数和
void get_primes(int n) {
    sd[1] = 1; // 1的约数和是1

    for (int i = 2; i <= n; i++) {  //遍历　2~n,筛质数的同时，筛出每个数字的约数和
        if (!st[i]) {               //如果i是质数
            primes[cnt++] = i;      //记录i到质数数组中
            sd[i] = num[i] = 1 + i; //质数的约数和是1+自身
        }
        for (int j = 0; primes[j] * i <= n; j++) {
            st[i * primes[j]] = true; //记录primes[j]的整数倍(i倍)是合数

            if (i % primes[j]) { //如果i不包含primes[j]这个质数因子
                sd[i * primes[j]] = sd[i] * sd[primes[j]];
                num[i * primes[j]] = primes[j] + 1;
            } else { //如果i包含了primes[j]这个质数因子
                sd[i * primes[j]] = sd[i] / num[i] * (num[i] * primes[j] + 1);
                num[i * primes[j]] = num[i] * primes[j] + 1;
                break;
            }
        }
    }
}

int main() {
    //记录开始时间
    clock_t begin = clock();
    // 1、暴力计算 O(n^2)
    // for (int i = 1; i <= n; i++) sum1[i] = bforce(i);
    // for (int i = 1; i <= n; i++) printf("%d ", sum1[i]);
    puts("");
    //记录结束时间
    clock_t end = clock();
    cout << "Running time:" << (double)(end - begin) / CLOCKS_PER_SEC * 1000 << "ms" << endl;

    // 2、通过筛法求出1到n的所有约数之和
    //记录开始时间
    begin = clock();
    for (int i = 1; i <= n; i++)         // O(n)
        for (int j = 2; j <= n / i; j++) // 调和级数O(logn) = n + n / 2 + n / 3 + ... + n/n = lnn + c
            sum2[i * j] += i;

    // for (int i = 1; i <= n; i++) printf("%d ", sum2[i]);
    puts("");
    //记录结束时间
    end = clock();
    cout << "Running time:" << (double)(end - begin) / CLOCKS_PER_SEC * 1000 << "ms" << endl;

    // 3、利用欧拉定理筛出约数和
    //记录开始时间
    begin = clock();
    get_primes(n);
    // for (int i = 1; i <= n; i++) printf("%d ", sd[i]-i);
    puts("");
    //记录结束时间
    end = clock();
    cout << "Running time:" << (double)(end - begin) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
    return 0;
}