← 返回题目列表

Codeforces · 2037/G

G. 纳特兰探索

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

您正在探索令人惊叹的纳特兰地区!该区域由 $$$n$$$ 城市组成,每个城市的吸引力为 $$$a_i$$$。当且仅当 $$$i < j$$$ 且 $$$\gcd(a_i,a_j)\neq 1$$$ 时,存在从城市 $$$i$$$ 到城市 $$$j$$$ 的有向边,其中 $$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

从城市 $$$1$$$ 开始,您的任务是确定到达城市 $$$n$$$ 可以采取的不同路径总数,以 $$$998\,244\,353$$$ 为模。当且仅当访问的城市集不同时,两条路径才是不同的。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — 城市数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$2 \leq a_i \leq 10^6$$$) — 每个城市的吸引力。

输出

输出到达城市 $$$n$$$ 的不同路径总数,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

5
2 6 3 4 6

输出 #1

5

输入 #2

5
4 196 2662 2197 121

输出 #2

2

输入 #3

7
3 6 8 9 11 12 20

输出 #3

7

输入#4

2
2 3

输出#4

0

注意

在第一个示例中,五个路径如下:

- 城市 $$$1\rightarrow$$$ 城市 $$$5$$$
- 城市 $$$1\rightarrow$$$ 城市 $$$2\rightarrow$$$ 城市 $$$5$$$
- 城市 $$$1\rightarrow$$$ 城市 $$$2\rightarrow$$$ 城市 $$$3\rightarrow$$$ 城市 $$$5$$$
- 城市 $$$1\rightarrow$$$ 城市 $$$2\rightarrow$$$ 城市 $$$4\rightarrow$$$ 城市 $$$5$$$
- 城市 $$$1\rightarrow$$$ 城市 $$$4\rightarrow$$$ 城市 $$$5$$$

在第二个示例中,两条路径如下:

- 城市 $$$1\rightarrow$$$ 城市 $$$3\rightarrow$$$ 城市 $$$5$$$
- 城市 $$$1\rightarrow$$$ 城市 $$$2\rightarrow$$$ 城市 $$$3\rightarrow$$$ 城市 $$$5$$$