一、题意抽象

• 给定长度为 $n$ 的正整数序列 $\{a_i\}_{i=1}^n$，且题目对每个公差 $d=1,2,\dots,n$ 构造一个等差数列

  $$b_i = i\cdot d,\quad i=1,2,\dots,n.$$

• 定义

  $$S_d = \sum_{i=1}^n [\,a_i \mid b_i\,],$$

  其中 $[\,\cdot\,]$ 是指示函数，“1” 表示条件成立，“0” 表示不成立。也就是说，$S_d$ 就是数有多少个下标 $i$ 使得 $a_i$ 能整除 $b_i=i\cdot d$。

• 要求最终答案

  $$\sum_{d=1}^n S_d.$$

朴素做法：对每个 $d$ 枚举所有 $i$，判断 $i\cdot d \bmod a_i\==0$。最坏是 $O(n^2)$，当 $n$ 达到 $10^5$ 时不可行。

---

二、数学化简

二、观察与数学化简

判断条件

$$a_i \mid (i\cdot d) \;\Longleftrightarrow\; i\cdot d \equiv 0 \pmod{a_i} \;\Longleftrightarrow\; d \equiv 0 \pmod{\frac{a_i}{\gcd(a_i,i)}}. $$

令

$$g_i = \gcd(a_i,\,i), \quad A_i' = \frac{a_i}{g_i}. $$

则上式等价于

$$A_i' \mid d.$$

也就是说，对于固定的 $i$，只有当 $d$ 是 $A_i'$ 的倍数时，$[\,a_i \mid i\cdot d\,]$ 才为 1。

因此

$$S_d \;=\;\sum_{i=1}^n \bigl[\,A_i'\mid d\,\bigr],$$

我们要求

$$\sum_{d=1}^n S_d =\sum_{d=1}^n \sum_{i=1}^n \bigl[\,A_i'\mid d\,\bigr] =\sum_{i=1}^n \sum_{d=1}^n \bigl[\,A_i'\mid d\,\bigr]. $$

对于固定的 $i$，在 $1\le d\le n$ 中满足 $A_i'\mid d$ 的一共有 $\displaystyle \left\lfloor \tfrac{n}{A_i'}\right\rfloor$ 个。

于是

$$\sum_{d=1}^n S_d =\sum_{i=1}^n \Bigl\lfloor \frac{n}{A_i'}\Bigr\rfloor =\sum_{i=1}^n \Bigl\lfloor \frac{n}{\,a_i/g_i\,}\Bigr\rfloor. $$

---

三、从思路到代码

1. 读取输入：$n$，数组 $a[1\ldots n]$。

2. 遍历每个下标 $i$：

   • 计算 $g = \gcd(i,\,a_i)$；
   • 令 $A' = a_i / g$；
   • 累加答案 += $\lfloor n / A' \rfloor$。

3. 输出累加结果。

此算法中每步 $\gcd$ 和一次除法、一次整除计数，都是 $O(\log n)$ 级别，整体 $O(n\log n)$，可轻松处理 $n=10^5$。

---

四、代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;

    ll ans = 0;  // 最终答案累加器

    // 逐个读取 a_i，并即时累加对答案的贡献
    for (ll i = 1; i <= n; i++) {
        ll ai;
        cin >> ai;

        // 1. 计算 g = gcd(i, ai)
        ll g = std::gcd(i, ai);

        // 2. 化简后得到 A' = ai / g
        //    只有当 d 是 A' 的倍数时，(i, d) 配对才算 valid
        ll Ap = ai / g;

        // 3. 在 d = 1..n 范围内，A' 的倍数共有 floor(n/Ap) 个
        ans += n / Ap;
    }

    // 输出最终累加值
    cout << ans << "\n";
    return 0;
}