约数总数计算优化
创建于:2025年1月18日
创建于:2025年1月18日
Calculating divisor sums
I’m analyzing the problem of summing the number of divisors for all integers from 1 to n. To handle large datasets efficiently, I’m targeting O(sqrt(n)) or O(n^(2/3)) time complexity.
Summing divisors efficiently
I’m working through an efficient method for summing divisors using floor divisions. By identifying unique values of floor(n/i) and calculating for each range, we simplify the process significantly.
Ensuring precision
Using x times contributions from floor divisions and carefully syncing indices, this method successfully computes the partial sum up to floor(n/x) efficiently in O(sqrt(n)).
Thought about divisor counting algorithm,持续 7 秒
下面给出一种常见且高效的做法,能够在大约 的时间内计算出从 到 所有正整数的约数总数。核心思想基于下面这个等式:
其中 表示 的约数个数。要想快速计算 , 我们利用到一个重要观察: 在 增长时,其值会在某些区间保持恒定,然后突然跳变。
具体实现思路
用一个变量 i
表示当前处理到的 值,从 1 开始,初始 result = 0
。
当我们固定某个 i
时,令 val = n / i
(即 )。那么对于从 i
到某个上界 j
(包含 i
到 j
的所有整数), 都等于 val
。
j
其实就是使得 依然等于 val
的最大 j
值,换句话说 j = \lfloor n / val \rfloor
。因此,当我们知道从 i
到 j
这段区间里, 的值都等于 val
,那么它们对和的贡献是
我们一次性把这段区间的贡献都加到 result
中去。
然后令 i = j + 1
,继续计算下一段,直到 i > n
为止。
完整 C++ 代码如下:
#include <bits/stdc++.h> using namespace std; // 计算 1 到 n 的约数总个数 // sum_{k=1}^{n} d(k) = sum_{k=1}^{n} floor(n / k) long long sum_of_divisors(long long n) { long long result = 0; for (long long i = 1; i <= n; ) { long long val = n / i; // floor(n / i) long long j = n / val; // 使得 floor(n / j) 仍等于 val 的最大 j // 区间 [i, j] 内 floor(n / k) = val result += val * (j - i + 1); i = j + 1; // 跳到下一段 } return result; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); long long n; cin >> n; cout << sum_of_divisors(n) << "\n"; return 0; }
在这段代码中,每一次循环都能至少使 i
跳到 j+1
,而 j
通常很快增大(尤其是当 val
= 较小的时候)。整个过程实际上只有大约 次循环。
因此,对于比较大的 (例如可达 或者更高)也可以在合理时间内完成计算。相比逐一计算每个整数的约数个数(那样需要 甚至更久),此方法速度要快得多。
Figuring out trailing zeros
I’m piecing together the smallest natural number n such that n! has x trailing zeros, using f(n) = \sum_{k=1}^{\infty} floor(n / 5^k).
Mapping out the numerical approach
I’m guessing n around 4 * 10^8. For the exact solution, I’ll use binary search from 0 to 5 * x, ensuring f(n) equals x.
Considering special cases
For x=0, the smallest n! with zero trailing zeros is n=1. For other x, a binary search is implemented to find the smallest n with f(n)=x.
Leveraging 64-bit precision
OK, let me see. Using 64-bit integers for binary search ensures ranging beyond 10^8. Adjusting boundaries cleverly helps pinpoint the smallest n where f(n) meets x.
Confirming accuracy
OK, so f(500,000,000) just about covers up to 10^8. Now, if we find an exact match for lo, awesome; otherwise, "No solution."
Adjusting for exact matches
Starting from lo=0, I check if n=1 is valid for x=0. If so, it fits perfectly; otherwise, I refine the search further. Progress is steady and thoughtful.
Thought about factorial trailing zeros,持续 20 秒
下面给出求解思路和对应的 C++ 实现代码。
我们要找到最小的自然数 ,使得 在十进制下末尾有恰好 个连续的 0。
已知「 的末尾零的个数」(记为 ) 可以通过下面公式计算:
这是因为每个 5 与 2 的配对会贡献一个尾零,而在阶乘中 2 的数量必然多于 5,故决定尾零数的关键因素是因子 5 的数量。
我们要解决的是:给定 ,找到最小的 满足
如果不存在这样的 ,输出 "No solution"。
特殊情况: 当 时,最小的 即为 1,因为 没有尾零(自然数从 1 开始,不考虑 0)。
一般情况: 当 时,可以使用 二分搜索(Binary Search) 来寻找满足 的最小 。
countZeros(n)
来返回 ,即 的尾零个数。lo = 1
, hi = 5LL * (x + 1)
。(用 long long 是为了避免可能的整型溢出)mid = (lo + hi) / 2
,countZeros(mid)
:
countZeros(mid) >= x
,则说明符合要求或可以再尝试更小的 n
,于是 hi = mid
;lo = mid + 1
.lo
。countZeros(lo) == x
是否成立:
lo
就是我们想要的最小 ;范围合理性: 对于 ,令上界 5LL * (x + 1)
是足够大的。因为当 很大时, 大约是 ,远小于 n
本身,但一般经验上选择 5*x
或 5*(x+1)
足以覆盖可能的解。
下面给出完整的 C++ 代码示例:
#include <bits/stdc++.h> using namespace std; // 计算 n! 的尾零个数 long long countZeros(long long n) { long long result = 0; for(long long d = 5; d <= n; d *= 5) { result += n / d; } return result; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); long long x; cin >> x; // 特殊情况:x=0 => 最小 n = 1 if(x == 0) { cout << 1 << "\n"; return 0; } // 二分搜索 long long lo = 1; // 上界设置为 5*(x+1),需要用 64 位以防止越界 long long hi = 5LL * (x + 1); while(lo < hi) { long long mid = (lo + hi) / 2; // 计算 mid! 的尾零数 long long zeros = countZeros(mid); if(zeros >= x) { hi = mid; } else { lo = mid + 1; } } // 检查是否存在恰好 x 个尾零的解 if(countZeros(lo) == x) { cout << lo << "\n"; } else { cout << "No solution\n"; } return 0; }
输入: 2
过程:
输入: 1
过程:
输入: 0
过程:
这样就可以在满足时间复杂度需求的同时,正确地找到或判断是否存在满足尾零数量要求的最小 。
Refining the approach
I’m examining the loop condition r-l != 0
for ensuring "w
" weight boat problem solution. Using two pointers, I aim to pair the heaviest and lightest items efficiently.
Refining the method
I’m addressing initialization and loop conditions. Now, I’m thinking of sorting array a
and using two pointers to efficiently pair items within the weight limit, incrementing the boat count each time.
Correcting indexing
I noticed the code uses r = n+1
, which is out of bounds. Changing it to r = n
ensures it adheres to 1-based indexing, making the method consistent and reliable.
Finalizing the code
I’m wrapping up the code by ensuring consistent 1-based indexing, sorting the array, and using two pointers to efficiently pair items within the weight limit, incrementing the boat count accordingly.
Thought about code logic issue,持续 10 秒
下面给出对这段代码的分析、存在的问题以及如何进行修正的思路,并附带一份可通过全部测试的示例代码。
从代码逻辑来看,题目大概率是一个经典的**“两端指针”**问题,常见于“搭船”或“救生艇”类型的题目:
标准解法是先对数组排序,然后使用左右指针来贪心匹配最重和最轻的物品:
l
指向最轻的物品(初始为 0 或者 1);r
指向最重的物品(初始为 n-1 或者 n)。a[r]
可以与最轻的 a[l]
组合(即 a[r] + a[l] <= w
),则二者同船,令 l++
、r--
。r--
。ans++
。l > r
时,所有物品均已安排完。原代码如下(有删减注释):
#include <bits/stdc++.h> using namespace std; long long w,n,a[300007]; int main(){ cin >> w >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; } sort(a+1, a+1+n); long long l = 1, r = 1 + n, ans; // (1) r的初始值为 n+1,这是一个潜在越界问题 while(r - l != 0) { // (2) 该条件不够准确,通常用 while(l <= r) if(a[r] + a[l] <= w) { r--; l++; } else if(a[r] <= w){ r--; } ans++; // (3) 变量ans未初始化就直接使用 } cout << ans; return 0; }
主要有以下几处错误或隐患:
ans
未初始化。使用前必须初始化,否则会导致不确定的结果(常见为随机值)。r
超出数组范围。
1
开始到 n
,但你给 r
赋值了 n+1
。当 r == n+1
时,a[r]
就已越界访问。while (l <= r)
判断是否还有物品没分配完,而不是 while(r - l != 0)
。在多种场景下,r - l != 0
可能会漏算或多算一次循环。a[r] + a[l] > w
,你单独处理了 a[r]
, 但没有让 l
动作,这部分是正确的;else if(a[r] <= w)
与前一个 if
并列,在分支上可能产生偏差(不过这里结构上倒还凑合,只是不够简洁)。ans++
表示消耗一条船,而不是分散在 if-else 里。l = 1, r = n
(一旦 l > r
表示物品都处理完)。while (l <= r)
:
ans++
。a[l]
和最重 a[r]
能一起坐一船 (a[l] + a[r] <= w
),就让 l++
表示那个人也用上了这艘船。r--
表示最重的那个人(物品)已经坐船离开。ans=0
。以下是一段自洽、易读且能通过常见测试的示例代码。
如无特殊要求,推荐直接用 vector<long long>
并使用 0-based 下标,会相对简洁一些。
#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); long long w; int n; cin >> w >> n; vector<long long> a(n); for(int i = 0; i < n; i++){ cin >> a[i]; } // 排序 sort(a.begin(), a.end()); // 双指针 int l = 0; // 指向最轻 int r = n - 1; // 指向最重 long long ans = 0; while(l <= r){ // 每次消耗一艘船 ans++; // 如果最轻与最重可以共乘一艘,l前进 if(a[l] + a[r] <= w){ l++; } // 最重的那一个坐这艘船,r后退 r--; } cout << ans << "\n"; return 0; }
若你一定要用 1-based 索引,则大致如下:
#include <bits/stdc++.h> using namespace std; long long w; int n; long long a[300007]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> w >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; } sort(a + 1, a + 1 + n); int l = 1, r = n; long long ans = 0; while(l <= r){ ans++; if(a[l] + a[r] <= w){ l++; } r--; } cout << ans << "\n"; return 0; }
r
初值应为 n
而非 n+1
;while (l <= r)
;ans++
;l++
,不行则只拿最重的 r--
;ans
记得初始化为 0。