# 算法题解：等差数列整除对总数（C++ 高效实现）
> **语言**：C++17
> **发布时间**：2026年1月1日
> **时间复杂度**：O(n log M)，M = max(aᵢ)
> **空间复杂度**：O(1)
> **关键词**：数论、gcd、贡献法、整除优化
---
## 🚀 C++ 代码实现（AC 友好）
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;
// 手写 gcd（C++17 可用 __gcd 或 std::gcd，但为兼容性自实现）
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
long long ans = 0;
// 遍历每个位置 i（从1开始编号）
for (int i = 1; i <= n; ++i) {
long long ai = a[i - 1];
long long g = gcd(ai, static_cast<long long>(i));
// 贡献值：floor(n * g / ai)
ans += (n * g) / ai;
}
cout << ans << '\n';
return 0;
}
✅ 正确性验证（对应样例）
输入：
4
2 2 3 1
计算过程：
| i | aᵢ | gcd(aᵢ, i) | 贡献 = ⌊4 × g / aᵢ⌋ |
|---|---|---|---|
| 1 | 2 | gcd(2,1)=1 | 4×1/2 = 2 |
| 2 | 2 | gcd(2,2)=2 | 4×2/2 = 4 |
| 3 | 3 | gcd(3,3)=3 | 4×3/3 = 4 |
| 4 | 1 | gcd(1,4)=1 | 4×1/1 = 4 |
| 总和 | 14 ✅ |
输出：
14
⚙️ 编译与运行建议
-
编译命令（推荐）：
g++ -std=c++17 -O2 -pipe -static -s solution.cpp -o solution -
输入输出重定向测试：
./solution < input.txt > output.txt 支持数据范围：n ≤ 2×10⁵，aᵢ ≤ 10⁹（使用
long long防溢出）
💡
n * g最大约为2e5 × 1e9 = 2e14，long long（最大约 9e18）可安全容纳。
🔍 算法核心思想回顾
转换求和顺序：
将
改为数论推导：
→ 满足条件的个数为
-
规避除零与溢出：
- 输入保证正整数，无需判 0
- 使用
long long防止中间结果溢出
> ✅ 代码已在本地用 GCC 11.4 + C++17 测试通过
> 📦 无 STL 以外依赖，适合 OJ / 面试手写
> 🌟 亮点：**手写 gcd 增强可移植性**、**I/O 加速提升性能**、**防溢出设计严谨**
