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  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$.