1061C.md (1683B)
1 Source: https://codeforces.com/problemset/problem/1061/C 2 3 C. Multiplicity 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an integer array $a_1, a_2, \ldots, a_n$. 22 23 The array $b$ is called to be a subsequence of $a$ if it is possible to remove some elements from $a$ to get $b$. 24 25 Array $b_1, b_2, \ldots, b_k$ is called to be good if it is not empty and for every $i$ ($1 \le i \le k$) $b_i$ is divisible by $i$. 26 27 Find the number of good subsequences in $a$ modulo $10^9 + 7$. 28 29 Two subsequences are considered different if index sets of numbers included in them are different. That is, the values of the elements do not matter in the comparison of subsequences. In particular, the array $a$ has exactly $2^n - 1$ different subsequences (excluding an empty subsequence). 30 31 Input 32 33 The first line contains an integer $n$ ($1 \le n \le 100\,000$) — the length of the array $a$. 34 35 The next line contains integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$). 36 37 Output 38 39 Print exactly one integer — the number of good subsequences taken modulo $10^9 + 7$. 40 41 Examples 42 43 Input 44 45 ``` 46 2 47 1 2 48 ``` 49 50 Output 51 52 ``` 53 3 54 ``` 55 56 Input 57 58 ``` 59 5 60 2 2 1 22 14 61 ``` 62 63 Output 64 65 ``` 66 13 67 ``` 68 69 Note 70 71 In the first example, all three non-empty possible subsequences are good: $\{1\}$, $\{1, 2\}$, $\{2\}$ 72 73 In the second example, the possible good subsequences are: $\{2\}$, $\{2, 2\}$, $\{2, 22\}$, $\{2, 14\}$, $\{2\}$, $\{2, 22\}$, $\{2, 14\}$, $\{1\}$, $\{1, 22\}$, $\{1, 14\}$, $\{22\}$, $\{22, 14\}$, $\{14\}$. 74 75 Note, that some subsequences are listed more than once, since they occur in the original array multiple times.