企业官网建设流程全解析

食品类网站模板,企业自建网站 备案,成都建设网站价格,天津微信网站建设目录 ​编辑 前言 一、约数的核心概念与性质 1.1 约数的定义 1.2 约数的核心性质 二、求单个整数的所有约数#xff1a;试除法的优化与实现 2.1 试除法的核心思路 2.2 避免重复与溢出的技巧 2.3 C 实现求单个整数的所有约数 2.4 代码测试与分析 三、求区间内所有数…目录​编辑前言一、约数的核心概念与性质1.1 约数的定义1.2 约数的核心性质二、求单个整数的所有约数试除法的优化与实现2.1 试除法的核心思路2.2 避免重复与溢出的技巧2.3 C 实现求单个整数的所有约数2.4 代码测试与分析三、求区间内所有数的约数集合倍数法的高效应用3.1 试除法的局限性3.2 倍数法的核心思路3.3 C 实现区间内所有数的约数集合3.4 时间复杂度分析四、约数个数定理与约数和定理公式法的应用4.1 约数个数定理4.2 约数和定理4.3 公式法求约数个数与约数和4.4 C 实现公式法求约数个数与约数和4.5 代码测试与优化五、实战例题 1牛客网 约数之和5.1 题目分析5.2 试除法解法实现5.3 代码分析六、实战例题 2牛客网 约数个数的和6.1 题目分析6.2 优化思路反向统计约数个数6.3 高效解法实现6.4 代码分析七、进阶优化数论分块优化约数个数和7.1 数论分块的核心思想7.2 数论分块的区间计算7.3 C 实现数论分块优化约数个数和7.4 时间复杂度分析八、常见误区与避坑指南8.1 数值溢出问题8.2 边界条件处理8.3 效率优化误区总结前言在算法竞赛的数论板块中约数相关问题是仅次于质数的高频考点。无论是求一个数的所有约数还是计算约数个数、约数和亦或是统计区间内所有数的约数集合这些问题看似独立实则都围绕着约数的核心性质展开。本文将从约数的基本概念出发层层拆解各类约数问题的求解思路带你彻底掌握约数相关问题的解题技巧让你在竞赛中轻松应对各类约数挑战。下面就让我们正式开始吧一、约数的核心概念与性质1.1 约数的定义约数又称因数是指整数 a 除以整数 bb≠0除得的商正好是整数而没有余数此时称 b 是 a 的约数记作 b|a。例如12 的约数有 1、2、3、4、6、12因为这些数都能整除 12 且没有余数。特别注意1 是所有正整数的约数一个数的最大约数是它本身最小约数是 1约数具有成对出现的性质如果 d 是 a 的约数那么 a/d 也一定是 a 的约数。例如 12 的约数中2 和 6 成对3 和 4 成对1 和 12 成对。1.2 约数的核心性质约数的成对出现性质是解决各类约数问题的关键它能将约数的枚举范围从 [1, a] 缩小到 [1, √a]极大地提升算法效率。例如要找出 100 的所有约数只需枚举 1 到 10√10010当找到一个约数 i 时即可同时得到另一个约数 100/i。此外约数还具有以下性质若 d 是 a 和 b 的约数则 d 也是gcd (a, b)的约数若 a 是 b 的倍数则 b 的所有约数也都是 a 的约数前提是 a 能被 b 整除。这些性质看似简单却是后续优化算法的重要依据在解决复杂约数问题时能起到事半功倍的效果。二、求单个整数的所有约数试除法的优化与实现2.1 试除法的核心思路根据约数成对出现的性质求单个整数 x 的所有约数时只需枚举 [1, √x] 范围内的所有整数 i若 i 能整除 x则 i 是 x 的约数同时 x/i 也是 x 的约数若 i x/i即 x 是完全平方数则只需记录一次避免重复。举个例子求 36 的所有约数√366枚举 1 到 6 的整数i136%10记录 1 和 36i236%20记录 2 和 18i336%30记录 3 和 12i436%40记录 4 和 9i536%5!0跳过i636%60636/6记录 6最终约数集合{1, 2, 3, 4, 6, 9, 12, 18, 36}。2.2 避免重复与溢出的技巧在代码实现中需要注意两个关键问题重复记录当 x 是完全平方数时i 和 x/i 相等此时只需记录一次数值溢出枚举条件若写成i*i x当 x 接近 1e12 时i*i 可能超出 int 范围因此推荐使用i x / i的写法既避免溢出又无需调用 sqrt 函数减少精度误差。2.3 C 实现求单个整数的所有约数#include iostream #include vector #include algorithm using namespace std; // 求x的所有约数返回有序列表 vectorint get_divisors(int x) { vectorint res; // 枚举到sqrt(x) for (int i 1; i x / i; i) { if (x % i 0) { res.push_back(i); // 避免重复记录完全平方数的约数 if (i ! x / i) { res.push_back(x / i); } } } // 排序使输出更规范 sort(res.begin(), res.end()); return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int x; cin x; auto divisors get_divisors(x); cout x 的约数有; for (int d : divisors) { cout d ; } cout endl; return 0; }2.4 代码测试与分析输入36输出36 的约数有1 2 3 4 6 9 12 18 36时间复杂度O (√x)。枚举范围从 x 缩小到√x效率大幅提升。对于 x1e12√x1e6仅需枚举 1e6 次完全可以在毫秒级完成。空间复杂度O (τ(x))其中 τ(x) 是 x 的约数个数约数函数。一个数的约数个数上限为 2√x如 x1e6 时约数个数最多为 100空间开销可忽略。三、求区间内所有数的约数集合倍数法的高效应用3.1 试除法的局限性当需要求 [1, n] 范围内所有数的约数集合时若对每个数单独使用试除法时间复杂度为O (n√n)。对于 n1e5n√n≈1e7.5虽然能通过但效率较低对于 n1e6n√n≈1e9会直接超时。此时需要一种更高效的方法 ——倍数法利用 “约数的倍数” 这一反向思维将时间复杂度优化至O (n log n)。3.2 倍数法的核心思路倍数法的本质是“反向枚举约数”对于每个约数 d[1, n] 中所有以 d 为约数的数都是 d 的倍数即 d, 2d, 3d, ..., kd其中 kd ≤n。因此我们可以枚举每个可能的约数 d从 1 到 n枚举 d 的所有倍数 md, 2d, ..., kd ≤n将 d 添加到 m 的约数集合中。举个例子求 [1, 6] 范围内所有数的约数集合d1倍数为 1,2,3,4,5,6 → 给每个数的约数集合添加 1d2倍数为 2,4,6 → 给 2,4,6 的约数集合添加 2d3倍数为 3,6 → 给 3,6 的约数集合添加 3d4倍数为 4 → 给 4 的约数集合添加 4d5倍数为 5 → 给 5 的约数集合添加 5d6倍数为 6 → 给 6 的约数集合添加 6最终结果1{1}2{1,2}3{1,3}4{1,2,4}5{1,5}6{1,2,3,6}3.3 C 实现区间内所有数的约数集合#include iostream #include vector using namespace std; const int MAXN 1e5 10; vectorint divisors[MAXN]; // divisors[m]存储m的所有约数 // 预处理[1, n]范围内所有数的约数集合 void pre_divisors(int n) { // 枚举每个约数d for (int d 1; d n; d) { // 枚举d的所有倍数m for (int m d; m n; m d) { divisors[m].push_back(d); } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; pre_divisors(n); // 输出每个数的约数集合 for (int m 1; m n; m) { cout m 的约数; for (int d : divisors[m]) { cout d ; } cout endl; } return 0; }3.4 时间复杂度分析倍数法的时间复杂度为O (n log n)这是因为对于约数 d其倍数个数为 n/d总操作次数为 n/1 n/2 n/3 ... n/n n (1 1/2 1/3 ... 1/n)括号内的部分是调和级数当 n 较大时调和级数的和约为log n γγ 为欧拉常数约 0.577因此总时间复杂度为O (n log n)。对于 n1e6n log n≈1e6×202e7完全可以在 1 秒内完成预处理效率远高于试除法。四、约数个数定理与约数和定理公式法的应用4.1 约数个数定理由算术基本定理任何大于 1 的自然数 n 都可以唯一分解为质因数的乘积其中 p₁p₂...pₖ为质数α₁,α₂,...,αₖ为正整数。约数个数定理指出n 的约数个数为所有质因子指数加 1 后的乘积即原理每个质因子 pᵢ可以选择 0 到 αᵢ个共 (αᵢ1) 种选择所有质因子的选择组合即为约数的总数。示例n122²×3¹约数个数为 (21)×(11)6分别是 1 (2⁰×3⁰)、2 (2¹×3⁰)、3 (2⁰×3¹)、4 (2²×3⁰)、6 (2¹×3¹)、12 (2²×3¹)。4.2 约数和定理约数和定理指出n 的所有约数之和为每个质因子的幂次和的乘积即原理将每个质因子的所有可能次幂相加再将结果相乘得到所有约数的和乘法分配律。示例n122²×3¹约数和为 (124)×(13)7×428验证123461228。4.3 公式法求约数个数与约数和结合质因数分解我们可以通过公式法快速计算约数个数和约数和步骤如下对 n 进行质因数分解得到标准分解式根据约数个数定理计算约数个数根据约数和定理计算约数和。4.4 C 实现公式法求约数个数与约数和#include iostream #include unordered_map using namespace std; // 质因数分解返回质因子及其指数 unordered_mapint, int prime_factor(int x) { unordered_mapint, int factors; for (int i 2; i x / i; i) { while (x % i 0) { factors[i]; x / i; } } if (x 1) { factors[x] 1; } return factors; } // 计算约数个数 int count_divisors(int x) { if (x 1) return 1; auto factors prime_factor(x); int res 1; for (auto [p, alpha] : factors) { res * (alpha 1); } return res; } // 计算约数和 long long sum_divisors(int x) { if (x 1) return 1; auto factors prime_factor(x); long long res 1; for (auto [p, alpha] : factors) { long long s 1; long long pow_p 1; // 计算1 p p^2 ... p^alpha for (int i 1; i alpha; i) { pow_p * p; s pow_p; } res * s; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; cout n 的约数个数 count_divisors(n) endl; cout n 的约数和 sum_divisors(n) endl; return 0; }4.5 代码测试与优化输入12输出12 的约数个数612 的约数和28优化点约数和计算中使用long long存储结果避免溢出如 n1e5 时约数和可能超过 int 范围质因数分解时同样使用i x / i的枚举条件避免溢出。五、实战例题 1牛客网 约数之和题目链接https://ac.nowcoder.com/acm/problem/221965.1 题目分析题目描述求自然数 N 的所有约数之和N≤1e4。输入一行一个正整数 N。输出一行一个整数表示 N 的约数和。示例输入10输出181251018。解题思路本题可使用试除法或公式法求解。由于 N≤1e4两种方法效率差异不大试除法实现更简洁。5.2 试除法解法实现#include iostream using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; long long sum 0; for (int i 1; i n / i; i) { if (n % i 0) { sum i; if (i ! n / i) { sum n / i; } } } cout sum endl; return 0; }5.3 代码分析时间复杂度O (√n)对于 n1e4√n100仅需枚举 100 次空间复杂度O (1)无需额外存储约数集合直接累加求和输入输出优化使用ios::sync_with_stdio(false);cin.tie(nullptr);提升读取速度。六、实战例题 2牛客网 约数个数的和题目链接https://ac.nowcoder.com/acm/problem/146826.1 题目分析题目描述给定 n求 1 到 n 的所有数的约数个数的和n≤1e6。输入一行一个正整数 n。输出一行一个整数表示答案。示例输入3输出51 的约数个数 1 2 的约数个数 2 3 的约数个数 2 5。核心难点若对每个数单独计算约数个数时间复杂度为 O (n√n)n1e6 时会超时。需利用倍数法的反向思维优化。6.2 优化思路反向统计约数个数根据倍数法的思想对于每个约数 d[1, n] 中以 d 为约数的数有 n/d 个即 d 的倍数个数。因此1 到 n 的约数个数的和等于所有 d 从 1 到 n 的 n/d 之和。示例n3d1倍数有 1,2,3 → 贡献 3d2倍数有 2 → 贡献 1d3倍数有 3 → 贡献 1总和3115与示例一致。6.3 高效解法实现#include iostream using namespace std; typedef long long LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; LL sum 0; // 枚举每个约数d贡献为n/d for (int d 1; d n; d) { sum n / d; } cout sum endl; return 0; }6.4 代码分析时间复杂度O (n)对于 n1e6仅需循环 1e6 次完全可以在 1 秒内完成空间复杂度O (1)仅需一个变量存储总和关键优化将 “求每个数的约数个数” 转化为 “统计每个约数的倍数个数”从 O (n√n) 优化到 O (n)效率大幅提升。七、进阶优化数论分块优化约数个数和7.1 数论分块的核心思想对于 n1e7O (n) 的时间复杂度可能会超时1e7 次循环约需 1 秒。此时可以使用数论分块又称整除分块进一步优化将时间复杂度降至 O (√n)。数论分块的核心观察对于连续的区间 [l, r]n/d 的值可能相同。例如 n10d1→10/110d2→10/25d3→10/33d4→10/42d5→10/52d6→10/61d7→10/71d8→10/81d9→10/91d10→10/101可以发现n/d 的值相同的区间为 [1,1]、[2,2]、[3,3]、[4,5]、[6,10]。对于每个区间 [l, r]n/d 的值为 k贡献为k*(r-l1)。7.2 数论分块的区间计算对于当前 lr 的计算方式为r n / (n /l)。例如 n10l4 时n/l2r10/25即区间 [4,5]。7.3 C 实现数论分块优化约数个数和#include iostream using namespace std; typedef long long LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; LL sum 0; // 数论分块l和r为当前区间的左右端点 for (int l 1, r; l n; l r 1) { r n / (n / l); sum (LL)(n / l) * (r - l 1); } cout sum endl; return 0; }7.4 时间复杂度分析数论分块的时间复杂度为O (√n)因为 n/d 的不同取值最多有 2√n 种当 d≤√n 时n/d 有√n 种取值当 d√n 时n/d√n也有√n 种取值。对于 n1e12√n1e6仅需循环 1e6 次效率极高。八、常见误区与避坑指南8.1 数值溢出问题约数和计算时未使用long long导致溢出如 n1e5 时约数和可能达到 1e10数论分块中(n/l)*(r-l1) 未强制转换为long longn1e6 时n/l1e6r-l11e6乘积为 1e12超出 int 范围。8.2 边界条件处理忽略 n1 的情况1 的约数个数为 1约数和为 1完全平方数的约数重复记录如 x4i2 时ix/i需只记录一次倍数法中枚举约数 d 时从 0 开始d0 不是任何数的约数应从 1 开始。8.3 效率优化误区对区间约数集合使用试除法n1e6 时超时约数个数和计算时未使用数论分块n1e7 时超时质因数分解时使用i*i x导致溢出应使用i x / i。总结除了掌握本文介绍的基础方法还需要多做综合性题目加深对约数性质的理解提升知识的融会贯通能力。如果你在学习过程中遇到具体题目无法解决或者想进一步了解约数与其他数论知识的结合应用可以随时留言交流。后续将持续更新数论进阶内容敬请关注