ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【题解】U405180 计算平方和 [打印本页]
作者: 圆咕噜咕噜    时间: 2024-4-24 20:24
标题: 【题解】U405180 计算平方和
欢迎大家在评论区抢前排！
\(\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}\) ，这个就是这道题目的难点，也是这道题为什么难度是 \(\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}\)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4