首页 > 其他分享 >【题解】U405180 计算平方和

【题解】U405180 计算平方和

时间:2024-02-05 15:35:51浏览次数:40  
标签:__ le U405180 题解 平方和 Part text int128 mathbf

\(\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}\) 。我们先来一起了解一下这个数据结构。

\(\mathbf{Part\ 2.1}\text{ C}\) + + 神奇整数类型之 \(\text{__int128 }/\ \mathbf{C}\) + + \(\mathbf{Magic\ integer\ type}\text{ __int128}\)

\(\mathbf{Part\ 2.1.1 }\text{ __int128}\) 是什么 \(/\ \mathbf{What\ is\ the }\text{ __int128}\)

标签:__,le,U405180,题解,平方和,Part,text,int128,mathbf
From: https://www.cnblogs.com/daiyulong/p/18008252/tijie-u405180

相关文章

  • [ARC162D] Smallest Vertices 题解
    题目链接点击打开链接题目解法这种树的形态计数题首先可以想到\(prufer\)序列计数,如果没有任何限制,那么方案数为\(\prod\frac{(n-2)!}{deg_i}\),其中\(deg_1=d_1-1,deg_i=d_i(2\lei\len)\)对于每个点分开求贡献考虑这个式子只和点的个数和子树内的\(\sumdeg\)有关......
  • P3604 美好的每一天 题解
    题目链接:美好的每一天经典题,这种字符串重排以后回文,优先考虑异或操作。考虑对一个字符串状态压缩,每个字符表示为\(1<<(c-97)\),然后将它们异或起来就可以得到一个字符串的状态压缩情况。考虑每一位异或情况,如果为偶数个单个字符则为\(0\),奇数则为\(1\),注意可以重排,那么当且仅......
  • 2024牛客寒假算法基础集训营1 J 又鸟之亦心 题解
    Question2024牛客寒假算法基础集训营1J又鸟之亦心Solution挺好的一个题,给了我很多启发显然,先二分最大值\(D\),关键在于\(check\)怎么写考虑到两个人是相对的,第\(i\)次之后肯定有一个人在\(a_i\),具体是谁不重要,也不需要关注是怎么走过来的,我们需要去维护另外一个人可......
  • 2024牛客寒假算法基础集训营1 K 牛镇公务员考试 题解
    Question2024牛客寒假算法基础集训营1K牛镇公务员考试给出一张试卷有\(n\)道单选题,每道题用一个整数\(a_i\)和一个长度为\(5\)的字符串\(s_i\)表示,其中第\(i\)道题的题面为:第\(a_i\)道题的答案是()A.\(s_1\)B.\(s_2\)C.\(s_3\)D.\(s_4\)E.\(s_5\)问:正......
  • [CF383E] Vowels 题解
    [CF383E]Vowels题解思路要求的这个东西一看就没什么性质,考虑枚举所有元音子集。如果我们能够求出\(f_s\)表示\(s\)集合作为元音时有多少个单词至少包含一个元音。难求,正难则反,考虑\(f_s\)表示\(s\)集合作为元音时有多少个单词全都由非元音字母组成,由于对称性,我们只......
  • Luogu「Daily OI Round 3」Simple 题解
    #include<iostream>#include<cstdio>#include<queue>#include<algorithm>#include<cstring>#include<string>#include<string.h>#include<vector>#defineintlonglong#definerep(a,b,c)for(autoa=b;a......
  • [ARC114D] Moving Pieces on Line 题解
    题目链接点击打开链接题目解法有点牛的题,前面的转化感觉很妙首先一个显然的性质是:一个棋子不可能走回头路,不然前面的路就白走了下面是最妙的一步:我们令\(st_i\)为\(i-1\toi\)和\(i\toi+1\)的颜色是否相同,那么问题可以转化成:选择\(\{p_i\}\),一开始所有点颜色为\(0\)......
  • ABC339 F Product Equality 题解
    QuestionABC339FProductEquality给出一个序列\(A_1,A_2,\cdots,A_N\)计算数对\((i,j,k)\)满足\(A_i\timesA_j=A_k\)的个数\(A_i\le10^{1000}\)Solution思考\(A_i\)比较小的情况如果\(A_i\le1e9\)的,暴力枚举\(i,j\)然后用\(map\)查找\(A_i\timesA_j......
  • gitlab 502问题解决
    问题现象: Whoops,GitLabistakingtoomuchtimetorespond.Tryrefreshingthepage,orgoingbackandattemptingtheactionagain.PleasecontactyourGitLabadministratorifthisproblempersists. 问题定位分析:一、查看系统资源使用情况磁盘满了g......
  • Linux服务器升级GLIBC失败导致shell不可用的问题解决经历
    转自https://blog.csdn.net/u010549608/article/details/126281354?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522170696599716800182728626%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=170696599716800182728626&biz_i......