简单题意：给定 [l,r]，求 [l<=i<j<=r] 的个数使得 (i-j)%k==0 数据范围：1<=l<=r<=1e9，1<=k<=1e9

首先需要知道一个引理，对于任意整数 ，都有其代数式为

回到原题，考虑原题式子，等价于求：

注意到下取整是一个黑盒函数，我们不能进行拆解，此时可以根据引理，有：

观察到， 还是一个黑盒，但此时可以通过放缩破除黑盒，即 可推导出 。所以有：

交换求和次序，有：

考虑内层边界， 的范围是：

则有 的范围是 ，此时可以去掉艾佛森括号：

观察 的范围，显然有：

（上面为什么要下取整，因为 有可能是小数，但 是整数，求和右边界不可能碰到小数部分）

所以有：

观察到，一共有 个数，所以原式可以变成：

观察上述式子，注意到，随着 的变化，每次就会减少一个 。不难想到等差数列优化，且不难看出末项在 时取到，即：

• 首项：
• 末项：
• 项数：

这题就做完了

代码：

#ifndef ONLINE_JUDGE
#include "dbg.h"
#endif
#include <bits/stdc++.h>
#define int long long
using namespace std;
int calc(int s,int e,int xs) {
    return(s+e)*xs/2;
}
void solve() {
    int l,r,k;cin>>l>>r>>k;
    int s=r-k-l+1;
    int xs=(r-l)/k;
    int e=r-k*xs-l+1;
    int ans=calc(s,e,xs);
    cout<<ans<<endl;
}
signed main() {
    int t=1;
    while(t--)solve();
}
/*
*/