← 返回题目列表

Codeforces · 1334/E

E. 除数路径

中文机器翻译题面 查看原题

给你一个正整数$$$D$$$。让我们根据它构建以下图表:

- 每个顶点都是 $$$D$$$ 的约数(不一定是素数,$$$1$$$ 和 $$$D$$$ 本身也包括在内);
- 如果 $$$x$$$ 可被 $$$y$$$ 整除且 $$$\frac x y$$$ 为素数,则两个顶点 $$$x$$$ 和 $$$y$$$ ($$$x > y$$$) 之间有无向边;
- 边的权重是 $$$x$$$ 的因数不是 $$$y$$$ 的因数。

例如,以下是 $$$D=12$$$ 的图表:

边 $$$(4,12)$$$ 的权重为 $$$3$$$,因为 $$$12$$$ 具有除数 $$$[1,2,3,4,6,12]$$$ 且 $$$4$$$ 具有除数 $$$[1,2,4]$$$。因此,$$$12$$$ 的约数 $$$3$$$ 不是 $$$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$$$ 为模。

示例

输入 #1

12
3
4 4
12 1
3 4

输出 #1

1
3
1

输入 #2

1
1
1 1

输出 #2

1

输入 #3

288807105787200
4
46 482955026400
12556830686400 897
414 12556830686400
4443186242880 325

输出 #3

547558588
277147129
457421435
702277623

注意

在第一个示例中:

- 第一个查询只是空路径 — 长度 $$$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$$$)。