Mertens funksiyası#3239

Mertens funksiyası

1 saniyə
128 meqabayt
Çox asan

Mobius funksiyası — XIX əsr alman riyaziyyatçısı, həmçinin Mobius zolağının kəşfi ilə də məşhur olan Avqust Ferdinand Mobiusun şərəfinə adlandırılmış multiplikativ ədədi funksiyadır.

Mobius funksiyası aşağıdakı kimi təyin olunur:

\mu(n)= \begin{cases} 1, & n=1,\\ 0, & \text{əgər } n \text{ sadə ədədin kvadratına bölünərsə},\\ (-1)^k, & \text{əgər } n \text{ } k \text{ müxtəlif sadə ədədin hasili şəklində göstərilə bilərsə}. \end{cases}

Mobius funksiyası Mertens funksiyası ilə aşağıdakı münasibətlə əlaqəlidir:

M(n)=\sum_{k=1}^{n}\mu(k).

Verilmiş hər bir ədədi üçün Mertens funksiyasının qiymətini hesablayın.

Giriş

Birinci sətirdə testlərin sayı t~(1\le t\le 10^5) verilmişdir.

Sonrakı sətrin hər birində tam ədəd n~(1\le n\le 10^7) verilmişdir.

Çıxış

Hər bir test üçün ayrı sətirdə Mertens funksiyasının qiymətini çap edin.

Nümunələr

Nümunə 1

Loading
Loading