【题解】U405180 计算平方和

这篇具有很好参考价值的文章主要介绍了【题解】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}\)

__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}\)

首先我们知道一个基础公式(这里我就不再赘述,不会的同学可以自行去网上查找):

\[1^2+2^2+3^2+\cdots+(n-2)^2+(n-1)^2+n^2=\frac{n\times(n+1)\times(2\times n+1)}6 \]

然后我们知道,线段的某个区域的长度是这么求的。

|_____________________________________________|
\(\ \ \ \ \ \ \ \ \ \ \ L\ \ \ \ \ \ \ \ \ \ \ \ \ R\)

\[L\sim R=R-L+1 \]

这个结论我们不难想到也可以运用到平方和公式上。我们可以下此结论:

\(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\)

好了,推完了,结论就是:

\[L^2+(L+1)^2+(L+2)^2+\cdots+(R-2)^2+(R-1)^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)\) 内计算平方和了。我厉不厉害?

有了这些方法,我们所有的问题就迎刃而解了!最后献出 \(\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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 模型评估(误差平方和(SSE The sum of squares due to error))

    举例:(下图中数据-0.2, 0.4, -0.8, 1.3, -0.7, 均为真实值和预测值的差) 在k-means中的应用: 公式各部分内容: 上图中: k=2 SSE图最终的结果,对图松散度的衡量. (eg:  SSE(左图)SSE(右图) ) SSE随着聚类迭代,其值会越来越小,直到最后趋于稳定: 如果质心的初始值选择不好,SSE只会达到一个不怎

    2024年02月04日
    浏览(49)
  • MATLAB知识点: SSE: 误差平方和、 MSE: 均方误差、RMSE: 均方根误差、MAE: 平均绝对误差、MAPE: 平均绝对百分比误差、SMAPE: 对称平均绝对百分比误差、R方: 决定系数

    ​讲解视频:可以在bilibili搜索《MATLAB教程新手入门篇——数学建模清风主讲》。​ MATLAB教程新手入门篇(数学建模清风主讲,适合零基础同学观看)_哔哩哔哩_bilibili 节选自第3章 3.4.2 算术运算 学完了矩阵的算术运算后,我们来做一些练习。 假设真实值是向量 ,拟合值或

    2024年02月21日
    浏览(42)
  • 蓝桥杯2023年第十四届省赛真题-平方差--题解

    时间限制: 3s 内存限制: 320MB 提交: 2379 解决: 469 给定 L, R,问 L ≤ x ≤ R 中有多少个数 x 满足存在整数 y,z 使得 x = y2 − z2。 输入一行包含两个整数 L, R,用一个空格分隔。 输出一行包含一个整数满足题目给定条件的 x 的数量。 复制 复制 1 = 1^2 − 0^2 ; 3 = 2^2 − 1^2 ; 4 =

    2024年02月07日
    浏览(50)
  • [BUUCTF]pwn栏目 warmup_csaw_2016 1的题解和小疑问,欢迎讨论

    首先非常感谢大家阅读我的第一篇。本文章不仅仅是题解,一些细枝末节的小问题也欢迎大家一起解答。 小问题的形式如Qx:xxxxxxx? 欢迎发现小问题并讨论~~ N1nE是本人另外一个名字,目前主要学习pwn方向,此文章以及后续别的文章,如有不当欢迎补充与纠正。 题目来自bu

    2023年04月08日
    浏览(29)
  • Python List - 计算列表平方

    整理9种Python常见的计算列表平方的方法: 此方法遍历列表中的每个数字,使用 ** 运算符计算其平方,然后将结果添加到新的列表中。 此方法使用列表推导式,这是一种更简洁的方式,可以在现有列表的每个项目上执行操作以创建新列表。 此方法使用map()函数和lambda函数来计

    2024年02月04日
    浏览(44)
  • chatgpt赋能python:Python怎么计算平方

    如果你是一名Python程序员,你一定会经常处理数字计算。在Python中,如果你需要计算一个数字的平方,你可以使用以下方法。 在Python中,乘方符号“**”可以用来表示指数运算。因此,如果你需要计算2的平方,你可以使用以下代码。 这将返回4。同样的,如果你需要计算3的平

    2024年02月07日
    浏览(44)
  • Python使用PyQt5实现计算平方或者立方

    此源码为直播时讲解的源码,我加了注释

    2024年02月11日
    浏览(36)
  • 欢迎来到IT时代----盘点曾经爆火全网的计算机电影

    计算机专业必看的几部电影,就像一场精彩的编程盛宴!《黑客帝国》让你穿越虚拟世界,感受高科技的魅力;《社交网络》揭示了互联网巨头的创业之路,《源代码》带你穿越时间解救世界,这些电影不仅带我们穿越到科技的前沿,还揭示了计算机科学背后的故事和挑战。

    2024年02月21日
    浏览(49)
  • Java——它要求用户输入一个整数(实际上是一个字符串),然后计算该整数的平方值,并将结果输出。

    这是一个Java程序,它要求用户输入一个整数(实际上是一个字符串),然后计算该整数的平方值,并将结果输出。程序的基本流程如下: 首先,声明并初始化变量data和result,它们的初始值都为0。 然后,输出提示信息,要求用户输入一个整数。 接下来,使用BufferedReader类从

    2024年02月11日
    浏览(39)
  • HAUE计算机学院OJ题解

    HAUE河工计院OJ1001 - 1050题解  HAUE河工计院OJ1050 - 1100题解  HAUE河工计院OJ1100 - 1150题解

    2024年02月10日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包