i_am_not_special's blog

????count increasing subsequence in O(n)
By i_am_not_special, history, 5 hours ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 hours ago, # |
  Vote: I like it +2 Vote: I do not like it

0(n) = 0 * n = 0, wtf??

→ Reply
  • »
    »
    5 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ?

    → Reply
    • »
      »
      »
      5 hours ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      ???

      u got me, you've just fixed that

      → Reply
      • »
        »
        »
        »
        4 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        do you have any solution for this problem?

        → Reply
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by i_am_not_special (previous revision, new revision, compare).

→ Reply
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by i_am_not_special (previous revision, new revision, compare).

→ Reply
»
2 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply