So the question is count the number of increasing subsequence such that the gcd of subsequence will be equal to 1.
1 <= size of array <= 1e5 1 <= a[i] <= 1e6
can anyone help me solve this problem.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3947 |
| 2 | ecnerwala | 3654 |
| 3 | jiangly | 3627 |
| 4 | jqdai0815 | 3620 |
| 5 | orzdevinwang | 3612 |
| 6 | Benq | 3586 |
| 7 | Radewoosh | 3582 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | ksun48 | 3474 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 163 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | atcoder_official | 155 |
| 5 | maroonrk | 152 |
| 6 | -is-this-fft- | 148 |
| 6 | SecondThread | 148 |
| 6 | cry | 148 |
| 9 | Petr | 147 |
| 10 | nor | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 08.08.2024 15:15:23 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
0(n) = 0 * n = 0, wtf??
?
???
u got me, you've just fixed that
do you have any solution for this problem?
Auto comment: topic has been updated by i_am_not_special (previous revision, new revision, compare).
Auto comment: topic has been updated by i_am_not_special (previous revision, new revision, compare).
Create a another array called primes which will have all the prime numbers in the given array in the same seqvence of the array and now create an another array called ream where ream[i] is how many numbers which are greater than primes[i] and right side of primes[i]. Now answer is sum of 2**k for each k in ream (pardon me if it's wrong).
For finding primes we can use Sieve of Eratosthenes.
For building ream array we can use merge sort (or) fenwick tree.