Задача №114977. Гладкие числа

Число называется \(b\)-гладким, если все его простые делители не превышают \(b\). Число \(x\) называется простым делителем числа \(y\), если \(y\) делится нацело на \(x\), \(x > 1\) и единственные два делителя числа \(x\) это \(1\) и \(x\).

Даны \(n\) и \(b\). Найдите количество \(b\)-гладких чисел от \(1\) до \(n\).

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

В единственной строке вводятся два целых числа \(n\) и \(b\) (\(4 \le n \le 10^{18}\), \(2 \le b \le 500\)).

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

В единственной строке выведите количество \(b\)-гладких чисел от \(1\) до \(n\).

Примечание

Во втором примере 3-гладкими числами от 1 до 12 являются: 1, 2, 3, 4, 6, 8, 9, 12

Система оценки

Тесты к этой задаче состоят из 18 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.

Доп. ограничения
Группа Баллы \(n\) \(b\) Необх. группы Комментарий}
0 0 – – – Тесты из условия.
1 7 \(n \le 10\,000\) \(b \le 100\) 0
2 8 \(n \le 10^7\) \(b \le 100\) 0, 1
3 8 \(n \le 10^{11}\) \(b \le 100\) 0 – 2
4 4 \(n \le 10^{11}\) \(b \le 300\) 0 – 3
5 6 \(n \le 10^{11}\) – 0 – 4
6 12 \(n \le 10^{16}\) \(b \le 100\) 0 – 3
7 7 \(n \le 10^{12}\) – 0 – 5
8 5 \(n \le 10^{13}\) – 0 – 5, 7
9 5 \(n \le 10^{14}\) – 0 – 5, 7, 8
10 9 – \(b \le 100\) 0 – 3, 6
11 4 – \(b \le 150\) 0 – 3, 6, 10
12 3 – \(b \le 200\) 0 – 3, 6, 10, 11
13 3 – \(b \le 250\) 0 – 3, 6, 10 – 12
14 3 – \(b \le 300\) 0 – 4, 6, 10 – 13
15 4 \(n \le 10^{15}\) – 0 – 5, 7 – 9
16 4 \(n \le 10^{16}\) – 0 – 9, 15, 16
17 4 \(n \le 10^{17}\) – 0 – 9, 15 – 17 Offline-проверка
18 4 – – 0 – 17 Offline-проверка
Примеры
Входные данные
7 2
Выходные данные
3
Входные данные
12 3
Выходные данные
8
Входные данные
10000 50
Выходные данные
2463
Сдать: для сдачи задач необходимо войти в систему