Функція Мертенса#3239

Функція Мертенса

1 секунда

128 мегабайтів

Дуже легка

Функція Мебіуса $μ (n)$ — мультиплікативна арифметична функція, названа на честь німецького математика XIX століття Августа Фердинанда Мебіуса, відомого також завдяки відкриттю стрічки Мебіуса.

Функція Мебіуса визначається наступним чином:

μ (n) = ⎩ ⎨ ⎧ 1, 0, (- 1)^{k}, n = 1, якщо n ділиться на квадрат простого числа, якщо n можна подати у вигляді добутку k різних простих чисел .

\mu(n)= \begin{cases} 1, & n=1,\\ 0, & \text{якщо } n \text{ ділиться на квадрат простого числа},\\ (-1)^k, & \text{якщо } n \text{ можна подати у вигляді добутку } k \text{ різних простих чисел}. \end{cases}

Функція Мебіуса пов'язана з функцією Мертенса $M (n)$ наступним співвідношенням:

M (n) = k = 1 \sum n μ (k) .

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

Обчисліть значення функції Мертенса $M (n)$ для кожного із заданих чисел $n$ .

Вхідні дані

У першому рядку задано кількість тестів $t (1 \leq t \leq 1 0^{5})$ t~(1\le t\le 10^5).

У кожному з наступних $t$ рядків задано ціле число $n (1 \leq n \leq 1 0^{7})$ n~(1\le n\le 10^7).

Вихідні дані

Для кожного тесту виведіть в окремому рядку значення функції Мертенса $M (n)$ .

Приклади

Приклад 1

μ (n) = ⎩ ⎨ ⎧ 1, 0, (- 1)^{k}, n = 1, якщо n ділиться на квадрат простого числа, якщо n можна подати у вигляді добутку k різних простих чисел .

M (n) = k = 1 \sum n μ (k) .

t (1 \leq t \leq 1 0^{5})

n (1 \leq n \leq 1 0^{7})