跳到主要内容
BlogArchiveAuthorsTags

P11495 [ROIR 2019] 两次测量 (Day 1)

· 阅读需 1 分钟
lailai
lailai
学生 & 开发者

题意简述​

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

∑i=lr∑j=i+1r[a∣j−i]\sum_{i=l}^{r}\sum_{j=i+1}^r[a\mid j-i]

解题思路​

∑i=lr∑j=i+1r[a∣j−i]=∑d=1r−l[a∣d](r−l−d+1)=∑k=1⌊r−la⌋(r−l−ka+1)=∑k=1⌊r−la⌋(r−l+1)−a∑k=1⌊r−la⌋k=⌊r−la⌋(r−l+1)−a⌊r−la⌋(⌊r−la⌋+1)2\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;
}