P11495题解

题意简述

给定正整数 $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}$$

参考代码

225 Bcpp

#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;
}