Qablar — Eolymp

Giriş

Birinci sətirdə $n$ və $Q$ tam ədədləri verilir ( $1 \leq n, Q \leq 3 \cdot 1 0^{6}$ 1 \leq n, Q \leq 3 \cdot 10^6).

İkinci sətirdə $n$ tam ədədi $a_{i}$ a_i verilir ( $2 \leq a_{i} \leq 5 \cdot 1 0^{5}$ 2 \leq a_i \leq 5 \cdot 10^5).

Növbəti $Q$ sətirdə $l_{i}$ l_i, $r_{i}$ r_i, $k_{i}$ k_i ədədləri verilir ( $1 \leq k \leq 5 \cdot 1 0^{5}$ 1 \leq k \leq 5 \cdot 10^5), ( $0 \leq l \leq r < n$ 0 \leq l \leq r < n).

Çıxış

$Q$ sətirdə, hər sorğu üçün sehr tətbiq edildikdən sonra bu qabların hamısında qalan mayenin ümumi miqdarını çıxarın.

Nümunələr

Nümunə 1

Loading

Qeyd

Birinci sorğuda, $l = 1$ l=1, $r = 3$ r=3, $k = 20$ k=20.

İndeksləri $1$ -dən $3$ -ə qədər olan qabları nəzərdən keçiririk: $a_{1} = 5$ a_1=5, $a_{2} = 3$ a_2=3, $a_{3} = 10$ a_3=10.

$5$ nömrəli qab üçün: $20$ ədəd $5$ -ə bölünür, amma $25$ -ə bölünmür, buna görə $\frac{20}{5} = 4$ \frac{20}{5}=4 qalacaq.

$3$ nömrəli qab üçün: $20$ ədəd $3$ -ə bölünmür, buna görə $20$ qalacaq.

$10$ nömrəli qab üçün: $20$ ədəd $10$ -a bölünür, amma $100$ -ə bölünmür, buna görə $\frac{20}{10} = 2$ \frac{20}{10}=2 qalacaq.

Deməli, birinci sorğunun cavabı $4 + 20 + 2 = 26$ 4+20+2=26-dır.

İkinci sorğuda, $l = 0$ l=0, $r = 4$ r=4, $k = 12$ k=12.

Bütün qabları nəzərdən keçiririk: $a_{0} = 2$ a_0=2, $a_{1} = 5$ a_1=5, $a_{2} = 3$ a_2=3, $a_{3} = 10$ a_3=10, $a_{4} = 2$ a_4=2.

$2$ nömrəli qablar üçün: $12$ ədədi $2^{2} = 4$ 2^2=4-ə bölünür, amma $2^{3} = 8$ 2^3=8-ə bölünmür, buna görə onların hər birində $\frac{12}{4} = 3$ \frac{12}{4}=3 qalacaq.

$5$ nömrəli qab üçün: $12$ ədədi $5$ -ə bölünmür, buna görə $12$ qalacaq.

$3$ nömrəli qab üçün: $12$ ədədi $3$ -ə bölünür, amma $9$ -a bölünmür, buna görə $\frac{12}{3} = 4$ \frac{12}{3}=4 qalacaq.

$10$ nömrəli qab üçün: $12$ ədədi $10$ -a bölünmür, buna görə $12$ qalacaq.

Deməli, ikinci sorğunun cavabı $3 + 12 + 4 + 12 + 3 = 34$ 3+12+4+12+3=34-dür.

Üçüncü sorğuda, $l = 2$ l=2, $r = 3$ r=3, $k = 100$ k=100.

Qabları nəzərdən keçiririk: $a_{2} = 3$ a_2=3, $a_{3} = 10$ a_3=10.

$3$ nömrəli qab üçün: $100$ ədədi $3$ -ə bölünmür, buna görə $100$ qalacaq.

$10$ nömrəli qab üçün: $100$ ədədi $1 0^{2} = 100$ 10^2=100-ə bölünür, buna görə $\frac{100}{100} = 1$ \frac{100}{100}=1 qalacaq.

Deməli, üçüncü sorğunun cavabı $100 + 1 = 101$ 100+1=101-dir.

Beləliklə, nümunə üçün düzgün cavablar $26$ , $34$ , $101$ -dir.

Bal hesablama

Alt tapşırıq $1$ ( $10$ xal): ( $n, Q \leq 1 0^{3}$ n, Q \le 10^3)
Alt tapşırıq $2$ ( $10$ xal): ( $a_{i} = 2$ a_i = 2)
Alt tapşırıq $3$ ( $20$ xal): ( $a_{0} = a_{1} = a_{2} = \dots = a_{n - 1}$ a_0 = a_1 = a_2 = \ldots = a_{n - 1})
Alt tapşırıq $4$ ( $50$ xal): ( $l_{i} = 0, r_{i} = n - 1$ l_i = 0, r_i = n - 1)
Alt tapşırıq $5$ ( $50$ xal): (bütün $a_{i}$ a_i-lər sadə ədəddir)
Alt tapşırıq $6$ ( $50$ xal): ( $k_{0} = k_{1} = k_{2} = \dots = k_{Q - 1}$ k_0 = k_1 = k_2 = \ldots = k_{Q - 1})
Alt tapşırıq $7$ ( $50$ xal): (bütün $a_{i}$ a_i-lər $2^{k}$ 2^k formasındadır)
Alt tapşırıq $8$ ( $100$ xal): ( $n, Q \leq 1 0^{5}$ n, Q \leq 10^5)
Alt tapşırıq $9$ ( $110$ xal): Əlavə məhdudiyyətlər olmadan