\(\mathbf{Part\ 0}\) 目录 \(/\ \mathbf{Contents}\)
\(\mathbf{Part\ 1}\) 题目大意 \(/\ \mathbf{Item\ content}\)
共有 \(T\) 组数据。给定 \(L,R\) ,请你计算 \(L^2+(L+1)^2+(L+2)^2+\cdots+(R-2)^2+(R-1)^2\) 。
对于 \(100\%\) 的数据:\(1\le T\le 10^6,\ 1\le L\le R\le 10^{12}\) 。
\(\mathbf{Part\ 2}\) 题解 \(/\ \mathbf{Solution}\)
首先我们看一下数据范围(见上)。首先 \(T\le10^6\) ,那么算法的时间复杂度总体只可以是 \(O(n)\) ,每一组数据的计算的时间复杂度就只能是 \(O(1)\) 。然后是 \(L\le R\le 10^{12}\) ,这个就是这道题目的难点,也是这道题为什么难度是 \(\small\colorbox{yellow}{普及/提高-}\) 的原因了。这个数据的计算结果开到 \(\text{long long}\) 也不行。所以这就考虑到了我们日常的积累。\(\text{C}\) + + 中有一个整数类型是完全可以支持这个数据结构的,那就是 \(\text{__int128}\) 。我们先来一起了解一下这个数据结构。