一、一个数的约数个数有多少

\quad 取个例子，对于12而言，其约数有1,2,3,4,6,126个不同的约数。怎么快速的求出一个数的约数数目有多少个呢？可以对这个数进行质因子分解，分解成$N=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_n^{{\alpha }_n}$，这样其约数个数为$({\alpha }_1+1)\ast ({\alpha }_2+1)\ast ({\alpha }_n+1)$。理解起来也很简单，任意取一个数的质因子$p_i$取$0{\alpha }_i$次，将这些质因子相乘得到的结果即为这个数的一个约数。比如$12=2^2\ast 3^1$：

取$0个2和0个3，得约数1$取$1个2和0个3，得约数2$取$2个2和0个3，得约数4$取$0个2和1个3，得约数3$取$1个2和1个3，得约数6$取$2个2和1个3，得约数12$

这样就可以轻松求出这个数所有的约数。

#include <iostream> #include <map> using namespace std; const int MOD = 1e9 + 7; int main() { map<int, int> cnt; // 存放每个质因子出现次数 int num; cin >> num; while(num -- ) { int n; cin >> n; for(int i = 2; i * i <= n; i ++ ) while(n % i == 0) n /= i, cnt[i] ++ ; if(n > 1) cnt[n] ++ ; } long long res = 1; for(auto &[p, a] : cnt) res = res * (a + 1) % MOD; cout << res << endl; return 0; }

二、约数之和

\quad 继上面这个问题，再求解约数的和。对于$12=2^2\ast 3^1$来说，其约数之和为$2^0\ast 3^0+2^1\ast 3^0+2^2\ast 3^0+2^0\ast 3^1+2^1\ast 3^1+2^2\ast 3^1=(2^0+2^1+2^2)\ast (3^0+3^1)$。借助这个例子，我们轻易可得： 对于任意正整数$N=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_n^{{\alpha }_n}$，其约数之和为$(p_1^0+\cdots +p_1^{{\alpha }_1-1})\ast \cdots \ast (p_n^0+\cdots +p_n^{{\alpha }_n-1})$。给个例题：

#include <iostream> #include <map> using namespace std; const int MOD = 1e9 + 7; int main() { int n; cin >> n; map<int, int> cnt; while(n -- ) { int t; cin >> t; for(int i = 2; i * i <= t; i ++ ) while(t % i == 0) t /= i, cnt[i] ++ ; if(t > 1) cnt[t] ++ ; } long long res = 1; for(auto &[base, a] : cnt) { long long temp = 1, p = base; for(int i = 0; i < a; i ++ ) temp = (temp + p) % MOD, p = base * p % MOD; res = res * temp % MOD; } cout << res << endl; return 0; }

三、求1~n中每个数的约数的和$O(\sqrt{n})$

\quad 输入一个整数n，输出$1,2,...,n$中每个数的约数的和。例如当n=3时，1有1个约数1；2有2个约数1,2；3有2个约数1,3。故而输出为5。下面给出时间复杂度为$O(\sqrt{n})$的做法。 \quad 首先我们可以得到约数和公式$y=\frac{n}{1}+\frac{n}{2}+\cdots +\frac{n}{n}$，直接这样做时间复杂度为$O(n)$。我们将公式看做一个函数：$y={\sum }_{x=1}^{x=n}\frac{n}{x},x为正整数$。这样相当于求$y=\frac{n}{x}$这个曲线与x轴围成的面积（只是相当于，毕竟这是离散点）。$y=\frac{n}{x}$这个曲线关于$y=x$对称，交点在$\sqrt{x}$处。故而其面积可以分为三部分计算：

$y=\sqrt{x}，y轴和y=\frac{n}{x}$围成的部分$s1$$y=\sqrt{x},x=\sqrt{x},x轴和y轴$围成的部分$s2$$x=\sqrt{x}，x轴和y=\frac{n}{x}$围成的部分$s3$

\quad 由于$y=\frac{n}{x}$关于$y=x$对称，故而$s1=s3$。$s1+s2$的面积即为${\sum }_{x=1}^{x=\sqrt{n}}\frac{n}{x}，x为正整数$，$s2$面积为$int(\sqrt{x})\ast int(\sqrt{x})$。令$t=int(\sqrt{x})$最终可得$y=s1+s2+s3=2\ast {\sum }_{x=1}^{x=t}\frac{n}{x}-t\ast t$。时间复杂度为$O(\sqrt{n})$。

long long solve(long long n) { long long sum = 0; int t = sqrt(n); for (int i = 1; i <= t; i++) sum += n / i; // s1 + s2 面积 sum *= 2; // 2 * s1 + 2 * s2 面积 sum -= t * t; // 2 * s1 + s2 = s1 + s2 + s3 return sum; }