B2060

FuriousC · 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;
}