CF2037G Natlan Exploring

你正在探索美丽的纳特兰地区！该地区由 $n$ 个城市组成，每个城市都有一个吸引力值 $a_i$。当且仅当 $i < j$ 且 $\gcd(a_i, a_j) \neq 1$ 时，城市 $i$ 到城市 $j$ 存在一条有向边，其中 $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。 你从城市 $1$ 出发，你的任务是计算到达城市 $n$ 的不同路径总数，对 $998\,244\,353$ 取模。只有当经过的城市集合不同，路径才被认为是不同的。

第一行包含一个整数 $n$（$2 \leq n \leq 2 \times 10^5$）——城市的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$2 \leq a_i \leq 10^6$）——每个城市的吸引力值。

输出从城市 $1$ 到城市 $n$ 的不同路径总数，对 $998\,244\,353$ 取模。

在第一个样例中，有五条路径如下： - 城市 $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$ 由 ChatGPT 4.1 翻译