【题解】U405180 计算平方和

欢迎大家在评论区抢前排！
\(\mathbf{Part\ 0}\) 目录 \(/\ \mathbf{Contents}\)


目录

• \(\mathbf{Part\ 0}\) 目录 \(/\ \mathbf{Contents}\)
  
• \(\mathbf{Part\ 1}\) 题目大意 \(/\ \mathbf{Item\ content}\)
  
• \(\mathbf{Part\ 2}\) 题解 \(/\ \mathbf{Solution}\)
  
  
  
  • \(\mathbf{Part\ 2.1}\text{ C}\) + + 神奇整数类型之 \(\text{__int128 }/\ \mathbf{C}\) + + \(\mathbf{Magic\ integer\ type}\text{ __int128}\)
    
    
    
    • \(\mathbf{Part\ 2.1.1}\) 快读 \(/\ \mathbf{fast\ read}\)
      
    • \(\mathbf{Part\ 2.1.2}\) 快写 \(/\ \mathbf{fast\ write}\)
      
    
    
  • \(\mathbf{Part\ 2.2}\) 平方和公式 \(/\ \mathbf{Sum\ of\ squares formula}\)
    
  • \(\mathbf{Part\ 2.3}\) \(\text{std}\) 代码和标准时空 \(/\ \mathbf{Std\ code\ and\ standard\ space-time}\)
    
  
  

\(\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}\) ，这个就是这道题目的难点，也是这道题为什么难度是 \(\colorbox{yellow}{普及/提高-}\) 的原因了。这个数据的计算结果开到 \(\text{long long}\) 也不行。所以这就考虑到了我们日常的积累。\(\text{C}\) + + 中有一个整数类型是完全可以支持这个数据结构的，那就是 \(\text{__int128}\) 。我们先来一起了解一下这个数据结构。
\(\mathbf{Part\ 2.1}\text{ C}\) + + 神奇整数类型之 \(\text{__int128 }/\ \mathbf{C}\) + + \(\mathbf{Magic\ integer\ type}\text{ __int128}\)

\(\text{__int128}\) 就是占用了 \(128\) 字节的整数存储类型。由于是二进制，范围就是 \(-2^{127}\sim2^{127}-1\) ，如果使用了 \(\text{unsigned __int128}\) ，则范围变成 \(0 \sim 2^{128}-1\) ，即约 \(39\) 位数，这在一定程度上可以替代高精度运算实现大数运算，而且操作难度更低，所以在数据范围不超过的情况下，都可以使 \(\text{__int128}\) 。
由于 \(\text{__int128}\) 只能实现四则运算，不能用  \(\text{cin,cout,scanf,printf}\) 输入输出，我们首先应该写个快读和快写的函数。
\(\mathbf{Part\ 2.1.1}\) 快读 \(/\ \mathbf{fast\ read}\)

快读模板（函数 \(\text{read}\) ）

1. __int128 read() {
2.     __int128 x=0,f=1;
3.     char c=getchar();
4.     while(c<'0'||c>'9') {
5.         if(c=='-') {
6.           f=-1;
7.           c=getchar();
8.         }
9.     }
10.     while(c>='0'&&c<='9') {
11.         x=x*10+c-'0';
12.         c=getchar();
13.     }
14.     return x*f;
15. }

复制代码

时间 \(/\ \mathbf{Time}\)空间 \(/\ \mathbf{Memory}\)代码长度 \(/\ \mathbf{Code\ length}\)语言 \(/\ \mathbf{Language}\)\(\text{2.17s}\)\(\text{684.00KB}\)\(\text{659B}\)\(\text{C++14 (GCC 9) O2}\)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！