Codeforces Round 988 (Div. 3) |
---|
Finished |
You are exploring the stunning region of Natlan! This region consists of n cities, and each city is rated with an attractiveness ai. A directed edge exists from City i to City j if and only if i<j and gcd, where \gcd(x, y) denotes the greatest common divisor (GCD) of integers x and y.
Starting from City 1, your task is to determine the total number of distinct paths you can take to reach City n, modulo 998\,244\,353. Two paths are different if and only if the set of cities visited is different.
The first line contains an integer n (2 \leq n \leq 2 \cdot 10^5) — the number of cities.
The second line contains n integers a_1, a_2, \ldots, a_n (2 \leq a_i \leq 10^6) — the attractiveness of each city.
Output the total number of distinct paths you can take to reach City n, modulo 998\,244\,353.
52 6 3 4 6
5
54 196 2662 2197 121
2
73 6 8 9 11 12 20
7
22 3
0
In the first example, the five paths are the following:
In the second example, the two paths are the following:
Name |
---|