约数-倍数法

2020-08-04 本文已影响0人 dachengquan

求1~n每个数的正约数集合-倍数法

以d为正约数的数有 $d,2d,3d,4d....\lfloor n/d \rfloor*d$ 从1到n扫描每个数，将每个数的倍数的正约数集合都加入d。
时间复杂度： $O(N+N/2+N/3+..+N/N) = O(N \log N)$

vector<int> a[50010];
void get_div(int n){
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n/i;j++)
            a[i*j].push_back(i);
    }
}