Олимпиадный тренинг

Задача . E. Пути по делителям

Задача

Темы: графы жадные алгоритмы Комбинаторика математика теория чисел *2200

Задано целое положительное число $D$. Построим из него следующий граф:

каждая вершина является делителем $D$ (не обязательно простым, $1$ и $D$ тоже включаются);
между двумя вершинами $x$ и $y$ ($x > y$) есть неориентированное ребро, если $x$ делится на $y$ и $\frac x y$ — простое число;
вес ребра — это количество делителей $x$, которые не являются делителями $y$.

Например, граф для $D=12$:

$\text{[math]}$

У ребра $(4,12)$ вес $3$, потому что у $12$ делители $[1,2,3,4,6,12]$, а у $4$ делители $[1,2,4]$. Поэтому существует $3$ делителя $12$, которые не являются делителями $4$ — $[3,6,12]$.

Между $3$ и $2$ нет ребра, потому что $3$ не делится на $2$. Между $12$ и $3$ нет ребра, потому что $\frac{12}{3}=4$ не простое число.

Длина пути между некоторыми вершинами $v$ и $u$ в графе равна сумме весов ребер в нем. Например, длина пути $[(1, 2), (2, 6), (6, 12), (12, 4), (4, 2), (2, 6)]$ равен $1+2+2+3+1+2=11$. Длина пустого пути равна $0$.

Тогда кратчайший путь между двумя вершинами $v$ и $u$ — это путь, длина которого минимальна.

Два пути $a$ и $b$ различны, если либо содержат различное количество ребер, либо существует такая позиция $i$, что ребра $a_i$ и $b_i$ различны.

Даны $q$ запросов вида:

$v$ $u$ — посчитайте количество кратчайших путей между вершинами $v$ и $u$.

Ответ может быть довольно большим, поэтому выведите его по модулю $998244353$.

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

В первой строке записано одно целое число $D$ ($1 \le D \le 10^{15}$) — число, из которого строится граф.

Во второй строке записано одно целое число $q$ ($1 \le q \le 3 \cdot 10^5$) — количество запросов.

В каждой из следующих $q$ строк записаны два целых числа $v$ и $u$ ($1 \le v, u \le D$). Гарантируется, что $D$ делится и на $v$, и на $u$ (и $v$, и $u$, являются делителями $D$).

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

Выведите $q$ целых чисел — для каждого запроса выведите количество кратчайших путей между двумя данными вершинами по модулю $998244353$.

Примечание

В первом примере:

на первый запрос только пустой путь — длина $0$;
на второй запрос пути $[(12, 4), (4, 2), (2, 1)]$ (длина $3+1+1=5$), $[(12, 6), (6, 2), (2, 1)]$ (длина $2+2+1=5$) и $[(12, 6), (6, 3), (3, 1)]$ (длина $2+2+1=5$).
на третий запрос только путь $[(3, 1), (1, 2), (2, 4)]$ (длина $1+1+1=3$).

Примеры

№	Входные данные	Выходные данные
1	12 3 4 4 12 1 3 4	1 3 1
2	1 1 1 1	1
3	288807105787200 4 46 482955026400 12556830686400 897 414 12556830686400 4443186242880 325	547558588 277147129 457421435 702277623

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет