Задача №114661. Хорошие массивы
Совсем недавно Вася узнал, что числа можно делить друг на друга нацело. Невероятно воодушевленный этим знанием, он стал изучать массивы, в которых одни числа делятся на другие. Вася называет массив из \(n\) целых положительных чисел \(a_1,\ a_2,\ a_3,\ \ldots,\ a_n\) хорошим , если для любого \(i\) от 1 до \(n - 1\) число \(a_i\) делится нацело на число \(a_{i + 1}\). Вася очень любит изучать хорошие массивы, а поэтому ему интересно, сколько всего существует хороших массивов размера \(n\), все числа в которых не превосходят \(c\).
В единственной строке даны два целых числа \(n\) и \(c\) (\(1 \le n, c \le 5 \cdot 10^7\)) — количество чисел в массиве и максимальное значение чисел в массиве.
Выведите единственное число — количество хороших массивов из \(n\) целых положительных чисел, не превосходяших \(c\). Так как искомое количество массивов может быть слишком большим, выведите его по модулю \(998\,244\,353\).
В первом примере подходят следующие массивы: \((1, 1, 1)\), \((2, 1, 1)\), \((3, 1, 1)\), \((2, 2, 1)\), \((3, 3, 1)\), \((2, 2, 2)\), \((3, 3, 3)\).
Во втором примере удовлетворят условиям 14 массивов: \((1, 1)\), \((2, 1)\), \((3, 1)\), \((4, 1)\), \((5, 1)\), \((6, 1)\), \((2, 2)\), \((4, 2)\), \((6, 2)\) \((3, 3)\), \((6, 3)\), \((4, 4)\), \((5, 5)\), \((6, 6)\).
Тесты к этой задаче состоят из 7 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Дополнительные ограничения | |||||
| Группа | Баллы | \(n\) | \(c\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 15 | \(n \le 10\) | \(c \le 10\) | 0 | |
| 2 | 14 | \(n \le 1000\) | \(c \le 1000\) | 0, 1 | |
| 3 | 12 | \(n \le 5000\) | \(c \le 5000\) | 0 – 2 | |
| 4 | 16 | \(n \le 100\,000\) | \(c \le 100\,000\) | 0 – 3 | |
| 5 | 14 | \(n \le 10^6\) | \(c \le 10^6\) | 0 – 4 | |
| 6 | 15 | \(n \le 10^7\) | \(c \le 10^7\) | 0 – 5 | |
| 7 | 14 | – | – | 0 – 6 | Offline-проверка. |
3 3
7
2 6
14