欢迎大家在评论区抢前排!
\(\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\ 2.1}\text{ C}\) + + 神奇整数类型之 \(\text{__int128 }/\ \mathbf{C}\) + + \(\mathbf{Magic\ integer\ type}\text{ __int128}\)
\(\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}\) )
__int128 read() {
__int128 x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') {
f=-1;
c=getchar();
}
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
\(\mathbf{Part\ 2.1.2}\) 快写 \(/\ \mathbf{fast\ write}\)
快写模板(函数 \(\text{print}\) )
void print(__int128 x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>9) {
print(x/10);
}
putchar(x%10+'0');
}
解决完了数据类型的问题,我们该想想算法。怎样在 \(O(1)\) 的时间复杂度内计算 \(L^2+(L+1)^2+(L+2)^2+\cdots+(R-2)^2+(R-1)^2\) 呢?我相信,聪明的你一定想到了数学。让我们一起在评论区打出 让我们来探索一下数学的奥秘!数学好闪,拜谢数学!
这几个字(怎么说说就说出这种话)!
\(\mathbf{Part\ 2.2}\) 平方和公式 \(/\ \mathbf{Sum\ of\ squares formula}\)
首先我们知道一个基础公式(这里我就不再赘述,不会的同学可以自行去网上查找):
然后我们知道,线段的某个区域的长度是这么求的。
|_____________________________________________|
\(\ \ \ \ \ \ \ \ \ \ \ L\ \ \ \ \ \ \ \ \ \ \ \ \ R\)
这个结论我们不难想到也可以运用到平方和公式上。我们可以下此结论:
设 \(L^2+(L+1)^2+(L+2)^2+\cdots+(R-2)^2+(R-1)^2=\text{sum}(L,R)\) ,则 \(\text{sum}(L,R)=\text{sum}(1,R)-\text{sum}(1,L)+L^2\) 。
更详细的推导:
\(\ \ \ \ \text{sum}(L,R)\)
\(=\text{sum}(1,R)-\text{sum}(1,L)+L^2\)
\(=\frac{R\times(R+1)\times(2\times R+1)}6-\frac{L\times(L+1)\times(2\times L+1)}6+L^2\)
好了,推完了,结论就是:
这样就可以在 \(O(1)\) 内计算平方和了。我厉不厉害?文章来源:https://www.toymoban.com/news/detail-825016.html
有了这些方法,我们所有的问题就迎刃而解了!最后献出 \(\text{std}\) 代码和标准时空。文章来源地址https://www.toymoban.com/news/detail-825016.html
\(\mathbf{Part\ 2.3}\) \(\text{std}\) 代码和标准时空 \(/\ \mathbf{Std\ code\ and\ standard\ space-time}\)
#include<bits/stdc++.h>
using namespace std;
__int128 x;
__int128 read() {
__int128 num=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') {
f=-1;
}
c=getchar();
}
while(c>='0'&&c<='9') {
num=num*10+c-'0';
c=getchar();
}
return f*num;
}
void print(__int128 num) {
if(x<0) {
putchar('-');
x*=-1;
}
int ans[55]={},top=0;
do {
ans[top++]=num%10;
num/=10;
} while(num);
while(top) {
putchar(ans[--top]+'0');
}
}
int main() {
int t;
cin>>t;
while(t--) {
__int128 L=read(),R=read();
print(((R*(R+1)*(2*R+1))/6)-((L*(L+1)*(2*L+1))/6)+(L*L));
putchar('\n');
}
return 0;
}
时间 \(/\ \mathbf{Time}\) | 空间 \(/\ \mathbf{Memory}\) | 代码长度 \(/\ \mathbf{Code\ length}\) | 语言 \(/\ \mathbf{Language}\) |
---|---|---|---|
\(\text{2.17s}\) | \(\text{684.00KB}\) | \(\text{659B}\) | \(\text{C++14 (GCC 9) O2}\) |
到了这里,关于【题解】U405180 计算平方和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!