学习笔记——数论——约数

1.d/n 等价于n%d==0. 2.一个整数N的约数个数的上界为. 3.1-N 每个数的约数个数综合大约为N * log N 个。 4.1-1e9中的数,约数个数最多的数仅有1536个约数 倍数法求1-N中所有数的约数集合:NlogN void gao() { vectorfactor[M]; for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=i)v[j].push_back(i); } 数论分块: k/i (1<=i<=n) L,R每块的范围,x每块k/i的取值 for(int L=1,R;L<