题解与来源题共享。已有题解默认通过；新增或编辑后需由来源域管理员审核。待审核、驳回题解仅作者和审核管理员可见。来源域：system

• 0

  CYS LV 10 MOD @ 2025-7-6 19:22:14

  一、题意抽象

  • 给定长度为 $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;
  }