Fișierul intrare/ieșire gadfadar2.in, gadfadar2.out Sursă preONI 2023 6-7
Autor Vlad Tutunaru Adăugată de avatar vlad_TT Vlad Tutunaru vlad_TT
Timp de execuție pe test 0.569 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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 ≤ lr ≤ 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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii