#3729. 数字金字塔求和

数字金字塔求和

题目描述

题目描述

给定一个正整数 nn,请输出下面这个数字金字塔中所有数字的总和:

  • 第 11 行有 11 个数字 11;
  • 第 22 行有 22 个数字 22;
  • 第 33 行有 33 个数字 33;
  • ……
  • 第 ii 行有 ii 个数字 ii。

例如当 n=3n=3 时,金字塔为:

1
2 2
3 3 3

此时所有数字之和为 1+2+2+3+3+3=141+2+2+3+3+3=14。

请你计算并输出该金字塔所有数字的总和。

输入格式

输入一行一个正整数 nn。

输出格式

输出一行一个整数,表示金字塔中所有数字的总和。

样例

1
1 
3
14 

说明/提示

数据范围

  • 对于 100%100\% 的数据,1≤n≤10001 \le n \le 1000。

提示

第 ii 行有 ii 个数字 ii,因此第 ii 行数字之和为 i×i=i2i \times i = i^2。

所以总和为 12+22+⋯+n21^2 + 2^2 + \cdots + n^2,也可以直接逐行累加计算。

解析

解题思路

观察数字金字塔的构造规则:第 ii 行恰好有 ii 个数字,且每个数字都是 ii。因此第 ii 行的数字之和为

$$\underbrace{i+i+\cdots+i}_{i\text{ 个}} = i \times i = i^2.$$

于是整个金字塔所有数字的总和就是

12+22+32+⋯+n2.1^2 + 2^2 + 3^2 + \cdots + n^2.

我们只需要从 11 到 nn 枚举每一行,把该行的平方累加到答案中即可。

算法选择理由

本题数据范围只有 n≤1000n \le 1000,逐行累加的时间与空间开销都极小,代码也最直观、最不容易出错。虽然平方和存在公式

∑i=1ni2=n(n+1)(2n+1)6,\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6},

可以做到 O(1)O(1) 计算,但本题并不需要。使用循环写法还能自然地避免公式中乘法顺序或整数溢出等细节问题,同时与题目提示中“也可以直接逐行累加计算”一致。

复杂度分析

  • 时间复杂度:O(n)O(n),循环执行 nn 次,每次进行常数次运算。
  • 空间复杂度:O(1)O(1),只使用了若干整型变量。

实现细节

答案最大为 ∑i=11000i2≈3.34×108\sum_{i=1}^{1000} i^2 \approx 3.34 \times 10^8,虽然可以用 int 存储,但为了稳妥使用 long long。累加时写成 1LL * i * i,保证乘法在 64 位整数下进行,避免不必要的溢出风险。

来源

AI 生成 · 云端大模型(域):deepseek-chat · 入门 · 数学