Fișierul intrare/ieșire | gadfadar2.in, gadfadar2.out | Sursă | preONI 2023 6-7 |
---|---|---|---|
Autor | Vlad Tutunaru | Adăugată de | Vlad Tutunaru • vlad_TT |
Timp de execuție pe test | 0.569 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Gadfadar2
Am luat și noi, au dat și ei
Definim f(x) = numărul minim de pătrate perfecte a căror sumă să fie x. De exemplu f(13) = 2 pentru că 13 poate fi scris ca sumă de două pătrate perfecte: 32 + 22 = 9 + 4 = 13.
Cerință
Se dau numerele naturale Q și k. Să se răspundă la Q întrebări de forma ( l , r ):
Care este valoarea sumei: f(l) + f(l + k) + f(l + 2k) + ... + f(l + i ⋅ k) , unde l + i ⋅ k este cel mai mare număr mai mic sau egal cu r?
Date de intrare
Pe prima linie din fișierul de intrare gadfadar2.in se află numerele naturale Q și k separate prin câte un spațiu cu semnificația din enunț. Pe fiecare din următoarele Q linii se află câte două numere naturale l și r separate printr-un spațiu, reprezentând câte o întrebare.
Date de ieșire
În fișierul de ieșire gadfadar2.out se vor afișa Q numere naturale, câte unul pe fiecare rând, al i-lea număr reprezentând răspunsul la cea de-a i-a întrebare.
Restricții
- 1 ≤ Q ≤ 200.000
- 1 ≤ l ≤ r ≤ 100.000
- 1 ≤ k ≤ 100.000
Exemplu
gadfadar2.in | gadfadar2.out |
---|---|
5 3 1 10 5 18 69 420 100 999 13019 55910 |
8 12 350 814 40762 |
Explicație
Valorile funcției f pentru primele 18 valori sunt:
1 = 12 => f(1) = 1
2 = 12 + 12 => f(2) = 2
3 = 12 + 12 + 12 => f(3) = 3
4 = 22 => f(4) = 1
5 = 22 + 12 => f(5) = 2
6 = 22 + 12 + 12 => f(6) = 3
7 = 22 + 12 + 12 + 12 => f(7) = 4
8 = 22 + 22 => f(8) = 2
9 = 32 => f(9) = 1
10 = 32 + 12 => f(10) = 2
11 = 32 + 12 + 12 => f(11) = 3
12 = 22 + 22 + 22 => f(12) = 3
13 = 32 + 22 => f(13) = 2
14 = 32 + 22 + 12 => f(14) = 3
15 = 32 + 22 + 12 + 12 => f(15) = 4
16 = 42 => f(16) = 1
17 = 42 + 12 => f(17) = 2
18 = 32 + 32 => f(18) = 2
Astfel, pentru întrebarea l = 1, r = 10 răspunsul este f(1) + f(4) + f(7) + f(10) = 1 + 1 + 4 + 2 = 8.
Pentru l = 5, r = 18 răspunsul este f(5) + f(8) + f(11) + f(14) + f(17) = 2 + 2 + 3 + 3 + 1 = 12.