Problem description
Uwaga! To jest trudniejsza wersja zadania Tabliczka Krasnali. W tej wersji N = 106. Reszta treści jest bez zmian.
Jasiu bawi się swoją kolekcją krasnali. Postanowił ułożyć je w kwadratową siatkę o wymiarach N × N. Zauważył, że krasnal stojący w i-tym rzędzie i j-tej kolumnie posiada dokładnie i × j złotych monet (dla 1 ≤ i, j ≤ N).
Jasiu ma jednak swoją nielubianą liczbę X. Postanowił podliczyć całkowitą sumę złotych monet posiadanych przez wszystkie krasnale, pomijając jednak te krasnale, które mają dokładnie X złotych monet.
Twoim zadaniem jest napisanie programu, który obliczy i wypisze sumę złotych monet wszystkich krasnali, które nie posiadają ich dokładnie X.
Wejście
W pierwszym (i jedynym) wierszu wejścia znajduje się jedna liczba całkowita X – nielubiana liczba Jasia.
Wyjście
W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba całkowita – łączna suma złotych monet krasnali, które nie mają ich dokładnie X.
Ograniczenia
N = 106, 1 ≤ X ≤ N2.
Przykłady
| Wejście | Wyjście | Wyjaśnienie |
|
|
W tym przykładzie X = 1. Tylko jeden krasnal (w pierwszym rzędzie i pierwszej kolumnie) ma dokładnie 1 monetę. Suma monet wszystkich pozostałych krasnali wynosi 250000500000249999999999. |
| Wejście | Wyjście | Wyjaśnienie |
|
|
W tym przykładzie X = 11. Krasnale mające 11 monet stoją tylko na polach (1,11) oraz (11,1). Suma monet wszystkich pozostałych krasnali wynosi 250000500000249999999978. |
| Wejście | Wyjście | |
|
|