积性函数与线性筛 blogs 约数线筛 约数埃筛: vector<int> ys[500010]; void shaiys() { for(int i=1;i<=maxx;i++) for(int j=1;i*j<=maxx;j++) ys[i*j].push_back(i); } 莫比乌斯函数埃筛: void shai() { u[1]=1; for(int i=1;i<=maxx;i++) for(int j=2*i;j<=maxx;j+=i) u[j]-=u[i]; }