bhikkhu's blog

solving problems
By bhikkhu, 10 years ago, In English

I thought for many days about how do i solve this problem: http://codeforces.net/contest/475/problem/D But it seems to me that I cannot get any better than O(N^2). I think there is a knowledge gap(mathematics). I looked through the editorial too. But I cannot understand. I want to understand the solution. I even looked many of the submissions(using sparse tables, segment trees...). But staring the code doesn't seem to be beneficial(or may be I am too dumb for the problem). So, please help me solve this problem. I just want the idea. Thank you coders!

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

»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Look at authour's solution. At the end of each iteration divisors contain information about all possible intervals [L, R] with (L <= i && R == i) there will be at most 1 + Log(v[i]) different values for gcd on entire interval. divisors[42] is the number of such intervals with gcd value 42.

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

    Okay, so at each iteration divisors contains all unique gcd values along with the count of all (a, b) pairs [0, i]. My question is what is the logic. Also, how do I use the information that there will be at most 1 + log(v[i]) unique gcd values for a sequence starting with v[i]. I donot understand that. I would be thankful for any clarification.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Have you ever used EZ Collections? http://codeforces.net/blog/entry/14382 It can change everything!

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 6   Vote: I like it 0 Vote: I do not like it

    I don't use java. And I dont think it is related to this post too. Someone please answer my question.

    → Reply