题解：P11495 [ROIR 2019 Day 1] 两次测量

Heart_of_Iron · 2025-01-01 14:15:36 · 题解

思路

题目要求找到满足 l \leq i < j \leq r 且 a \mid (j - i) 的整数对 (i, j)。我们可以将问题重新表述如下：

1. 对于每个可能的 i，我们需要找到符合条件的 j，使得 j - i 是 a 的倍数，即： j = i + k \cdot a$$ 其中 $$k \geq 1 $$ 且 $$ i + k \cdot a \leq r
2. 这意味着对于每个 i，我们要找到满足以下条件的 k： i + k \cdot a \leq r$$ 即 $$k \leq \frac{r - i}{a}
3. 这样对于每个 i，我们可以直接计算符合条件的 k 的个数。每个 i 对应的 j 的个数是： \left\lfloor \frac{r - i}{a} \right\rfloor

   这表示对于每个 i，有多少个符合条件的 j。

4. 最终我们只需要对每个 i 从 l 到 r-1，计算对应的 j 的数量并累加即可。

   code

   
   #include<bits/stdc++.h>
   using namespace std;
   #define int unsigned long long//宏定义好习惯
   signed main()
   {
   int l, r, a;
   cin >> l >> r >> a;
   int cnt=0;//cnt
   for (int i = l; i < r; ++i)
       cnt += (r - i) / a;  // 这是通过 (r - i) / a 来计算符合条件的 k 的个数
   cout << cnt;//输出
   return 0;
   }

60 分。