Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

vidit_123's blog

By vidit_123, history, 15 months ago, In English,

Given an array,how to solve queries (10^5) of type Q:Value,L,R where value is a number and we need to report the count of all the numbers in the range [L,R] of the array such that gcd(Value,A[i])>1 where L<=i<=R. Given ARRAY SIZE :- 10^5 Each number 1<= A[i] <=10^5 TL = 1 Sec

 
 
 
 
  • Vote: I like it  
  • +16
  • Vote: I do not like it  

»
15 months ago, # |
  Vote: I like it +11 Vote: I do not like it

What are the constraints for the number of elements and the values (ai)?

  • »
    »
    15 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Sorry for this ,the Value of each 1<= A[i] <=100000 & Array size <=10^5

»
15 months ago, # |
Rev. 4   Vote: I like it +27 Vote: I do not like it

I'd like to know more details (time limit, amount of numbers in array and constraints on the numbers), but anyway, I'll share the solution that came to mind.

  • No number up to 109 has more than 1344 divisors, so we can find divisors of every element of array and store a list of positions that divide every number. This may or may not fit in memory or time, depending on the constraints. This step is , where M is the maximum value an array element can take.
  • Now for each query, make a list of the primes that divide Value. There are at most 9 such primes, because the product of the first 10 primes is  $>10^9$. Now for every possible mask of primes, check how many positions of range [L, R] divide their product with a binary search and use inclusion-exclusion principle. This process is O(29  *  logN) for each query, making the whole program O(Q * 29 * logN). This, again, may or may not fit in time depending on the constraints.
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    TL = 1 sec Array size is 10^5 And Each number is 1<=A[i]<=100000

    • »
      »
      »
      15 months ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      Then it should work. of the first step is OK for M ≤ 105 is OK. Now the second step has less complexity because the number of prime factors is at most 6, so it's O(Q * 26 * logN), which is also OK.

      Do you have an online judge where I can test the solution?

      • »
        »
        »
        »
        15 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        This was a subproblem of some other problem (tree based) .The link to the problem is https://www.codechef.com/problems/GTREE

        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think codechef problem is much easier than the one mentioned by you. Solution is similar but we can solve it without binary search just doing dfs and storing for each p how many numbers in current subtree are divisible by p.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it -73 Vote: I do not like it

    Can you explain this " store a list of positions that divide every number"?

  • »
    »
    9 months ago, # ^ |
    Rev. 4   Vote: I like it -31 Vote: I do not like it

    .

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How would you perform binary search in [L,R] to count no of positions?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u elaborate how you are doing the binary search to obtain count of elements in [L,R] which divisible a certain mask of primes?

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

this problem is from codechef march long challange..

it still running dude, don't cheat

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    look when the blog was published :)

    I think this is a problemsetter's codeforce account...

»
9 months ago, # |
  Vote: I like it -44 Vote: I do not like it

At first generate a list of primes that divide a number, for all number till M, the maximum number. This takes .

Now, for each number of the array ai, lets say the primes p1, p2, ..., pk divide that number, you can get this quickly from step 1. Go through all subsets of these primes. If a subset is pi1, pi2, ..., pir, then insert i to list pospi1·pi2... pir. This step takes O(26n).

Now when you receive a query X, take the primes p1, p2, ..., pk, that divides X, from the list generated at first. Now go through all of its subsets. Let the chosen subset be pi1, pi2, ..., pir, then count how many times a number from [l, r] appears in pospi1·pi2... pir. It can be done with two binary searches. If r is odd then add the count to answer, else subtract this count. It can be proven that this gives the answer, by inclusion-exclusion principal. Basically this counts number of numbers with at least one prime common with the query X. This step takes

  • »
    »
    9 months ago, # ^ |
      Vote: I like it -39 Vote: I do not like it

    talk is cheap, send code

  • »
    »
    9 months ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    What about the update in array element in the query?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      I don't see any mention of 'update' in this post. What are you talking about?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        Its my personal query.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it -15 Vote: I do not like it

          Lets say you change ai to x. First you need to reverse all changes that ai did, that means, go through all subsets of it's prime divisors and delete i from the list of their product. Then change ai to x, and again add it back.
          But as you need to keep the lists sorted to do binary search later, you can use balanced binary search trees, or just the policy based data structure in C++.

          If you have updates, then both query and update become

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    For those who are wondering who is "CodeChefFuckYou": please upvote this comment. Unless it has less than 100 upvotes I won't say his username(only that he is very good on Codeforces and you'll be surprised ^__^). He has a unique style of posting comments.

    For most interested: "&BYK&FM" — encrypted username, good luck!!

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it -6 Vote: I do not like it

»
9 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Why are you upvoting this post? It is cheating, and this post should be deleted immediately, I think because it violates CodeChef rules and principles of the competitive programming.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    This blog post was created 6 months ago. However the current interest in this post can be attributed to CodeChef's problem.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    This blog has nothing to do with CodeChef, the thing should be deleted is CodeChef problem. CodeChef should really care about problems of long challenge, because in 10 days even we can find code of problem from internet.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Sorry, I missed this fact. So it's good that later comments are downvoted and unclarified.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You also can do it with bitset. numbers less than 10^5 has less than 7 prime divisors. So for every primes less than 1e5 set the bit of positions of those numbers which are divided by.

GCD(x, a[i]) has no common prime divisors If their GCD is 1. you can travel through prime divisors and check how many numbers you can divide in the given range. then the ans might be (r-l+1- NumberofSetBit).

you can solve it easily than other technique.