== include(page="template/taskheader" task_id="gadfadar2") ==
Poveste și cerință...
bq. 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: 3[^2^] + 2[^2^] = 9 + 4 = 13.
h2. 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*$?
h2. Date de intrare
Fișierul de intrare $gadfadar2.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $gadfadar2.out$ ...
Î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.
h2. Restricții
* $... ≤ ... ≤ ...$
* 1 ≤ *Q* ≤ 200.000
* 1 ≤ *l* ≤ *r* ≤ 100.000
* 1 ≤ *k* ≤ 100.000
h2. Exemplu
table(example).
table(example).
|_. gadfadar2.in |_. gadfadar2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 3
1 10
5 18
69 420
100 999
13019 55910
| 8
12
350
814
40762
|
h3. Explicație
...
Valorile funcției f pentru primele 18 valori sunt:
1 = 1[^2^] => $f(1) = 1$
2 = 1[^2^] + 1[^2^] => $f(2) = 2$
3 = 1[^2^] + 1[^2^] + 1[^2^] => $f(3) = 3$
4 = 2[^2^] => $f(4) = 1$
5 = 2[^2^] + 1[^2^] => $f(5) = 2$
6 = 2[^2^] + 1[^2^] + 1[^2^] => $f(6) = 3$
7 = 2[^2^] + 1[^2^] + 1[^2^] + 1[^2^] => $f(7) = 4$
8 = 2[^2^] + 2[^2^] => $f(8) = 2$
9 = 3[^2^] => $f(9) = 1$
10 = 3[^2^] + 1[^2^] => $f(10) = 2$
11 = 3[^2^] + 1[^2^] + 1[^2^] => $f(11) = 3$
12 = 2[^2^] + 2[^2^] + 2[^2^] => $f(12) = 3$
13 = 3[^2^] + 2[^2^] => $f(13) = 2$
14 = 3[^2^] + 2[^2^] + 1[^2^] => $f(14) = 3$
15 = 3[^2^] + 2[^2^] + 1[^2^] + 1[^2^] => $f(15) = 4$
16 = 4[^2^] => $f(16) = 1$
17 = 4[^2^] + 1[^2^] => $f(17) = 2$
18 = 3[^2^] + 3[^2^] => $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.
== include(page="template/taskfooter" task_id="gadfadar2") ==
