自动搬运

查看原文

来自洛谷，原作者为

	lailai0916 Student & Developer

搬运于2025-08-24 23:07:51，当前版本为作者最后更新于2025-01-02 19:42:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

原题链接

• 洛谷 P11495 [ROIR 2019 Day 1] 两次测量

题意简述

给定正整数 $l,r,a$，计算：

$$\sum_{i=l}^{r}\sum_{j=i+1}^r[a\mid j-i]$$

解题思路

$$\begin{aligned} \sum_{i=l}^{r}\sum_{j=i+1}^r[a\mid j-i] &= \sum_{d=1}^{r-l} [a \mid d](r-l-d+1) \\ &= \sum_{k=1}^{\left\lfloor\frac{r-l}{a}\right\rfloor}(r-l-ka+1) \\ &= \sum_{k=1}^{\left\lfloor\frac{r-l}{a}\right\rfloor}(r-l+1)-a\sum_{k=1}^{\left\lfloor\frac{r-l}{a}\right\rfloor} k \\ &= \left\lfloor\frac{r-l}{a}\right\rfloor(r-l+1)-a\frac{\left\lfloor\frac{r-l}{a}\right\rfloor(\left\lfloor\frac{r-l}{a}\right\rfloor+1)}{2} \end{aligned} $$

参考代码

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

using ll=long long;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll l,r,a;
	cin>>l>>r>>a;
	cout<<((r-l)/a)*(r-l+1)-a*((r-l)/a)*((r-l)/a+1)/2<<'\n';
	return 0;
}