R2__D2's blog

By R2__D2, history, 6 years ago, In English

problem in brief:
problem link

you are given a Tree of nodes n(<=2e5). Each nodes has value x(<=2e5).

Let's denote the function g(x,y) as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex x to vertex y (including these two vertices).

For every integer from 1 to 2e5 you have to count the number of pairs (x,y)(1≤x≤y≤n) such that g(x,y) is equal to this number.

My idea:
As the number can be at most 2e5 so, the total number of divisors can be maximum 160.I just stored possible unique gcd for each node u where paths end at some nodes in subtree u. total numbers can be maximum 160 as well for each nodes. while traveling each node I calculated possible answers where paths start at some node in subtree u and ends at some nodes in subtree u. Finally when return back to parent node I cleared the memory of every childs to save memory.

Unfortunately, I got memory limit exceeded at test 100. but I have no idea why as I store values at only one node at a particular time.

my submission

Any suggestions will be appreciated.

Thanks.

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

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Instead of vectors take array of pairs.

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

    g[2e5][160][2] will easily cross memory limit.

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

      Not the adjacency list. Especially, the ones inside the dfs function.