C++ P3773 最小公倍数高效解法与实现详解

## 🔍 理解题目 P3773 P3773 是洛谷上的一道题目，全称为“最小公倍数”。该题通常与动态规划、数论（尤其是 LCM 性质）相关。题目大意是给定一个序列，求满足某种条件的子序列或子区间的最小公倍数之和等统计问题。 由于C++实现细节和题目输入输出格式高度相关，这里假设一个常见的版本：给定长度为 n 的序列 a，求所有长度 ≥ 2 的连续子区间的最小公倍数之和。若你提供具体输入格式或样例，我可以给出更精确的代码。 ## 💻 核心算法思路 需要计算每个连续子区间的 LCM。直接枚举所有子区间复杂度 O(n²) 且 LCM 计算量大，需优化。 利用性质：固定右端点 r，向左扩展左端点 l 时，LCM 会单调不降，且不同 LCM 值的数量为 O(log(max(a)))。因此可以维护一个列表，记录对每个右端点 r 而言，区间 [l, r] 的 LCM 值及其对应最小左端点。 处理时： - 初始化列表为空。 - 对每个右端点 r： - 新元素 a[r] 作为一个新的单元素区间 [r, r]，LCM 为 a[r]，左端点为 r。 - 将列表中的每一项与 a[r] 求 LCM，更新 LCM 值，并合并相同 LCM 的项（保留最小左端点）。 - 列表大小始终 ≤ O(log V)，V 为 a 中最大值。 - 对列表中每个项，累加 LCM * (当前左端点 - 上一个左端点) 到答案，注意区间长度需 ≥ 2，因此要排除单元素区间。 ## 🧩 C++ 实现示例 ```cpp #include <bits/stdc++.h> using namespace std; using ll = long long; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } int main() { int n; cin >> n; vector<ll> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; ll ans = 0; vector<pair<ll, int>> seg; // {LCM值, 左端点} for (int r = 0; r < n; ++r) { vector<pair<ll, int>> newSeg; newSeg.push_back({a[r], r}); for (auto &p : seg) { ll cur = lcm(p.first, a[r]); if (!newSeg.empty() && newSeg.back().first == cur) { newSeg.back().second = p.second; // 合并，保留更小的左端点 } else { newSeg.push_back({cur, p.second}); } } seg = newSeg; // 累加答案，排除长度为1的区间 int prev = r; // 当前右端点 r 的前一个位置，起始为 r（对应单元素区间） for (int i = 0; i < (int)seg.size(); ++i) { int L = seg[i].second; // 区间 [L, r] 的长度 = r - L + 1 // 对所有左端点 l 满足 L <= l <= prev，这一段的 LCM 都是 seg[i].first // 但要求 l <= r-1（长度≥2），因此有效左端点为 max(L, r) 到 prev int start = L; if (start > r) break; // 只考虑长度≥2的区间 if (start < r) { ans += seg[i].first * (min(prev, r-1) - start + 1); } prev = L - 1; if (prev < 0) break; } } cout << ans << endl; return 0; } ``` 代码中 `seg` 存储了按左端点从大到小排列的 (LCM, 左端点) 对，且 LCM 严格递增。累加时利用区间长度统计。 ## ⚠️ 注意事项 - 使用 `long long` 避免溢出，尤其是 LCM 较大时。 - 合并相同 LCM 时保留最小的左端点（即最靠左的起点），这样能正确覆盖所有子区间。 - 题目可能要求对结果取模，若需取模则在累加时 `ans %= MOD`。 ######[AI问答 | 1011点数解答 | 2026-08-23 18:59:53]