codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1829G.md (2221B)


      1 Source: https://codeforces.com/problemset/problem/1829/G
      2 
      3 G. Hits Different
      4 
      5 time limit per test
      6 
      7 2.5 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 In a carnival game, there is a huge pyramid of cans with $2023$ rows, numbered in a regular pattern as shown.
     22 
     23  ![](https://espresso.codeforces.com/944109fd35d631f1a6949221008cfab20655ee75.png)
     24 
     25 If can $9^2$ is hit initially, then all cans colored red in the picture above would fall.
     26 
     27 You throw a ball at the pyramid, and it hits a single can with number $n^2$. This causes all cans that are stacked on top of this can to fall (that is, can $n^2$ falls, then the cans directly above $n^2$ fall, then the cans directly above those cans, and so on). For example, the picture above shows the cans that would fall if can $9^2$ is hit.
     28 
     29 What is the sum of the numbers on all cans that fall? Recall that $n^2 = n \times n$.
     30 
     31 Input
     32 
     33 The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
     34 
     35 The only line of each test case contains a single integer $n$ ($1 \leq n \leq 10^6$) — it means that the can you hit has label $n^2$.
     36 
     37 Output
     38 
     39 For each test case, output a single integer — the sum of the numbers on all cans that fall.
     40 
     41 Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++). For all valid inputs, the answer will always fit into 64-bit integer type.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 10
     49 
     50 9
     51 
     52 1
     53 
     54 2
     55 
     56 3
     57 
     58 4
     59 
     60 5
     61 
     62 6
     63 
     64 10
     65 
     66 1434
     67 
     68 1000000
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 156
     75 1
     76 5
     77 10
     78 21
     79 39
     80 46
     81 146
     82 63145186
     83 58116199242129511
     84 ```
     85 
     86 Note
     87 
     88 The first test case is pictured in the statement. The sum of the numbers that fall is $$1^2 + 2^2 + 3^2 + 5^2 + 6^2 + 9^2 = 1 + 4 + 9 + 25 + 36 + 81 = 156.$$
     89 
     90 In the second test case, only the can labeled $1^2$ falls, so the answer is $1^2=1$.
     91 
     92 In the third test case, the cans labeled $1^2$ and $2^2$ fall, so the answer is $1^2+2^2=1+4=5$.
     93 
     94 In the fourth test case, the cans labeled $1^2$ and $3^2$ fall, so the answer is $1^2+3^2=1+9=10$.
     95 
     96 In the fifth test case, the cans labeled $1^2$, $2^2$, and $4^2$ fall, so the answer is $1^2+2^2+4^2=1+4+16=21$.