Need help on Educational Round 45 problem G( GCD Counting)

Revision en1, by R2__D2, 2018-06-28 11:33:32

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English R2__D2 2018-06-28 11:33:32 1324 Initial revision (published)