CF2037G.Natlan Exploring

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

你正在探索美丽的纳塔地区！该地区由 $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
```
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$

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页