Блог пользователя R2__D2

Автор R2__D2, история, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Instead of vectors take array of pairs.