Задача
Вкотре запізнившись на урок, Байтик, проходячи повз ігрову кімнату, помітив шахову дошку. Порахував усі клітинки на ній, і йому стало цікаво: скільки різних квадратів зі стороною $k(1 \leqslant k \leqslant n)$ можна розмістити на дошці розміру $n$.
Вхідні дані
Натуральне число $n$ $( n\leqslant 10000)$ розмір шахової дошки.
Вихідні дані
Єдине число – кількість різних квадратів, які можна розмістити на шаховій дошці.
Тести
| № | Входные данные | Выходные данные |
| 1 | 3 | 14 |
| 2 | 10 | 385 |
| 3 | 99 | 328350 |
| 4 | 999 | 332833500 |
| 5 | 10000 | 333383335000 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
import java.util.*; import java.lang.*; import java.io.*; import java.util.Scanner; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner i = new Scanner(System.in); long n = i.nextInt(); long result = n*(n + 1)*(2*n + 1) / 6; System.out.println(result); } } |
Рішення
Вирішити цю задачу можна за допомогою квадратного пірамідального числа — числа, яке висловлює кількість квадратів з різними сторонами в сітці $n$*$n$. Загальна формула для пірамідального числа порядку $n$: $\sum\limits_{k = 1}^{n} k^{2} = \frac{n(n+1)(2n+1)}{6}$. Використаємо виведену формулу для лінійного обчислення, щоб не використовувати цикли і зменшити час роботи програми.