题解：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;
}