Divisor Paths
Contest: Educational Codeforces Round 85 (Rated for Div. 2)
Difficulty rating: 2200
Tags: combinatorics, graphs, greedy, math, number theory

You are given a positive integer $$$D$$$. Let's build the following graph from it:

- each vertex is a divisor of $$$D$$$ (not necessarily prime, $$$1$$$ and $$$D$$$ itself are also included);
- two vertices $$$x$$$ and $$$y$$$ ($$$x > y$$$) have an undirected edge between them if $$$x$$$ is divisible by $$$y$$$ and $$$\frac x y$$$ is a prime;
- the weight of an edge is the number of divisors of $$$x$$$ that are not divisors of $$$y$$$.

For example, here is the graph for $$$D=12$$$:

Edge $$$(4,12)$$$ has weight $$$3$$$ because $$$12$$$ has divisors $$$[1,2,3,4,6,12]$$$ and $$$4$$$ has divisors $$$[1,2,4]$$$. Thus, there are $$$3$$$ divisors of $$$12$$$ that are not divisors of $$$4$$$ — $$$[3,6,12]$$$.

There is no edge between $$$3$$$ and $$$2$$$ because $$$3$$$ is not divisible by $$$2$$$. There is no edge between $$$12$$$ and $$$3$$$ because $$$\frac{12}{3}=4$$$ is not a prime.

Let the length of the path between some vertices $$$v$$$ and $$$u$$$ in the graph be the total weight of edges on it. For example, path $$$[(1, 2), (2, 6), (6, 12), (12, 4), (4, 2), (2, 6)]$$$ has length $$$1+2+2+3+1+2=11$$$. The empty path has length $$$0$$$.

So the shortest path between two vertices $$$v$$$ and $$$u$$$ is the path that has the minimal possible length.

Two paths $$$a$$$ and $$$b$$$ are different if there is either a different number of edges in them or there is a position $$$i$$$ such that $$$a_i$$$ and $$$b_i$$$ are different edges.

You are given $$$q$$$ queries of the following form:

- $$$v$$$ $$$u$$$ — calculate the number of the shortest paths between vertices $$$v$$$ and $$$u$$$.

The answer for each query might be large so print it modulo $$$998244353$$$.

Input format:
The first line contains a single integer $$$D$$$ ($$$1 \le D \le 10^{15}$$$) — the number the graph is built from.

The second line contains a single integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le D$$$). It is guaranteed that $$$D$$$ is divisible by both $$$v$$$ and $$$u$$$ (both $$$v$$$ and $$$u$$$ are divisors of $$$D$$$).

Output format:
Print $$$q$$$ integers — for each query output the number of the shortest paths between the two given vertices modulo $$$998244353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example:

- The first query is only the empty path — length $$$0$$$;
- The second query are paths $$$[(12, 4), (4, 2), (2, 1)]$$$ (length $$$3+1+1=5$$$), $$$[(12, 6), (6, 2), (2, 1)]$$$ (length $$$2+2+1=5$$$) and $$$[(12, 6), (6, 3), (3, 1)]$$$ (length $$$2+2+1=5$$$).
- The third query is only the path $$$[(3, 1), (1, 2), (2, 4)]$$$ (length $$$1+1+1=3$$$).

Example input:
12
3
4 4
12 1
3 4

Example output:
1
3
1

Example input:
1
1
1 1

Example output:
1

Editorial:
Let's define the semantics of moving along the graph. On each step the current number is either multiplied by some prime or divided by it.
I claim that the all shortest paths from $$$x$$$ to $$$y$$$ always go through $$$gcd(x, y)$$$. Moreover, the vertex numbers on the path first only decrease until $$$gcd(x, y)$$$ and only increase after it.
Let's watch what happens to the divisors list on these paths. At first, all the divisors of $$$x$$$ that are not divisors of $$$y$$$ are removed from the list. Now we reach gcd and we start adding the divisors of $$$y$$$ that are missing from the list. The length of the path is this total number of changes to the list. That shows us that these paths are the shortest by definition.
If we ever take a turn off that path, we either will add some divisor that we will need to remove later or remove some divisor that we will need to add later. That makes the length of the path not optimal.
Now let's learn to calculate the number of paths. The parts before gcd and after it will be calculated separately, the answer is the product of answers for both parts.
How many paths are there to gcd? Well, let's divide $$$x$$$ by $$$gcd$$$, that will give us the primes that should be removed from $$$x$$$. You can remove them in any order because the length of the path is always the same. That is just the number of their permutations with repetitions (you might also know that formula as multinomial coefficient).
The number of paths from $$$gcd$$$ to $$$y$$$ is calculated the same way.
To find the primes in $$$\frac{x}{gcd(x, y)}$$$ you can factorize $$$D$$$ beforehand and only iterate over the primes of $$$D$$$.
Overall complexity: $$$O(\sqrt{D} + q \log D)$$$.