Простые отары


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

На джайлоо у реки Чон-Кемин пасутся отары двух чабанов. В отаре Бакыта животные пронумерованы числами от 1 до A, у Эрлана — от 1 до B. Ветеринар осматривает пары животных (x, y): x из отары Бакыта, y из отары Эрлана. Пару он называет «простой», если наибольший общий делитель номеров НОД(x, y) — простое число.

Рисунок

Ответьте на q вопросов: сколько простых пар при данных A и B?

Входные данные

В первой строке — число q (1 ≤ q ≤ 5000). В каждой из следующих q строк — два целых числа A и B (1 ≤ A, B ≤ 10⁷).

Выходные данные

Для каждого вопроса выведите количество пар (x, y), 1 ≤ x ≤ A, 1 ≤ y ≤ B, у которых НОД(x, y) — простое число.

Пример 1

Вход:

3
4 4
10 7
1 100

Выход:

4
20
0

Пояснение

При A = B = 4 подходят пары (2, 2), (2, 4), (4, 2), (3, 3) — у них НОД равен 2 или 3. У пары (4, 4) НОД равен 4, это не простое число.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов A, B ≤ 300, ещё в 10 % тестов A, B ≤ 10⁶.

Подсказка

Функция Мёбиуса: Σ μ(d) по всем делителям d числа m равна 1 при m = 1 и 0 иначе.


Комментарии

Еще нет ни одного комментария.