自动搬运

查看原文

来自洛谷，原作者为

	FuriousC **

搬运于2025-08-24 21:03:06，当前版本为作者最后更新于2021-07-08 19:09:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

这里给出一种目前题解中没有的结论做法。

时间复杂度 $O(1)$。

首先题目只要我们求出此区间中 $17$ 的倍数之和，我们不难发现一个区间中所有 $17$ 的倍数 $\div 17$ 后得到的数组成了一个公差为 $1$ 的上升的等差数列。

拿样例举个栗子：$50$ 到 $85$ 中 $17$ 的倍数为 $51,68,85$；$\div 17$ 后得到了数列 $3,4,5$，所以样例的输出为 $(3+4+5)\times 17=204$。

我们又知道公差为 $1$ 的上升的等差数列的求和公式是 $($ 首项 $+$ 尾项 $)\times$ 项数 $\div 2$，所以就能解决这题啦。

但现在还有一个问题，怎么求出这个区间中第一个 $17$ 的倍数和最后一个 $17$ 的倍数呢？

其实很简单，我们可以直接求出区间中第一个 $17$ 的倍数和最后一个 $17$ 的倍数 $\div 17$ 得到的数，分别是 $\lceil l\div 17\rceil$ 和 $\lfloor r\div 17\rfloor$。

这样一来，问题就迎刃而解了。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	double l,r;//为了方便 floor 和 ceil 的使用，这里使用 double
	cin>>l>>r;
	double l1=ceil(l/17),r1=floor(r/17);//求出等差数列的首项和尾项
	cout<<(l1+r1)*(r1-l1+1)/2*17;//等差数列之和*17
	return 0;
}