【算法】约数个数、约数和
目录
【求⼀个整数的所有约数】
【求 [1, n] 每个数的约数集合】
【约数个数定理】
【求单个数的约数个数】
【约数和定理】
【求单个数的约数之和】
【求⼀个整数的所有约数】
对于⼀个整数 ，若 d 是 x 的约数，那么 x/d 也是 x 的约数。也就是说，除了完全平⽅数，约数
都是成对出现的。因此，可以⽤试除法求⼀个整数的所有约数。枚举 [1,根号n] 之间的整数，判断是否能整除。试除法也能求出⼀个整数的约数个数以及约数总和。
int d[N], cnt; // d 数组：记录所有约数，cnt：约数个数 void get_d(int x) { // 注意从 1 开始循环，1 可以是约数 for (int i = 1; i <= x / i; i++) { if (x % i == 0) // 如果 i 可以整除 x，说明 i 是 x 的约数 { d[cnt++] = i; if (i != x / i) d[cnt++] = x / i; } } }枚举到 根号n ，因此时间复杂度为 O( 根号N) 。由于约数通常成对出现，假设某个数，从 1
到 根号n 都是它的约数，那么⼀个整数 n 的约数个数的上限为 2*根号n。
【求 [1, n] 每个数的约数集合】
如果⽤试除法分别求每⼀个数的约数，时间复杂度过⾼（O（n*根号n）。可以反过来想，对于每个数 d， [1, n] 中以 d 为约数的数就是 d 的倍数。因此可以⽤倍数法求出 [1, n] 每个数的约数集合。枚举 [1, n] 中的数 ( i ) 的所有倍数（i*j），看看该倍数（i*j）是否 <= n，如果是，就在（i*j）这个数的约数集合中添加 i。
int n; vector<int> d[N]; // d[i] 是 i 的约数集合 void get_d() { for (int i = 1; i <= n; i++) // 枚举所有约数 for (int j = 1; j <= n / i; j++) // 约数的倍数 d[i * j].push_back(i); }【约数个数定理】
【求单个数的约数个数】
• 第⼀种⽅式：枚举 1 到 根号n 之间的整数；
int cnt; // cnt：约数个数 void get_d(int x) { // 注意从 1 开始循环，1 可以是约数 for (int i = 1; i <= x / i; i++) { if (x % i == 0) // 如果 i 可以整除 x，说明 i 是 x 的约数 { cnt++ if (i != x / i) cnt++; } } }• 第⼆种⽅式：在分解质因数的过程中，利⽤公式可以直接计算出某个数的约数个数
int c[N]; // c[i] 表⽰ i 这个质数出现的次数 // 比如 600 ：c[2] == 3、c[3] == 1、c[5] == 2 int ret; //约数个数 void sum_of_prime(int x) { for (int i = 2; i <= x / i; i++) // 注意防溢出 { int cnt = 0; while (x % i == 0) // 只要有这个因⼦，就除尽，并且计数 { x /= i; cnt++; } c[i] += cnt; } if (x > 1) c[x]++; // 不要忘记判断最后⼀个质数 // 公式可以直接计算出某个数的约数个数 for(int i = 2; i <= n; i++) if(c[i]) ret *= (c[i] + 1); }【约数和定理】
【求单个数的约数之和】
• 第⼀种⽅式：枚举1 到根号 n 之间的整数；
int sum; // sum：约数和 void get_d(int x) { // 注意从 1 开始循环，1 可以是约数 for (int i = 1; i <= x / i; i++) { if (x % i == 0) // 如果 i 可以整除 x，说明 i 是 x 的约数 { sum += i; if (i != x / i) sum += x / i; } } }• 第⼆种⽅式：在分解质因数的过程中，利⽤公式可以直接计算出某个数的约数总和。
int c[N]; // c[i] 表⽰ i 这个质数出现的次数 // 比如 600 ：c[2] == 3、c[3] == 1、c[5] == 2 int ret; //约数和 void sum_of_prime(int x) { for (int i = 2; i <= x / i; i++) // 注意防溢出 { int cnt = 0; while (x % i == 0) // 只要有这个因⼦，就除尽，并且计数 { x /= i; cnt++; } c[i] += cnt; } if (x > 1) c[x]++; // 不要忘记判断最后⼀个质数 // 公式可以直接计算出某个数的约数和 for(int i = 2; i <= n; i++) { if(c[i]) { int tmp = 1; for(int j = 1; j <= c[i]; j++) { tmp += pow(i,j); } ret *= tmp; } }