GCDCNT - Editorial

coolreshab · March 13, 2018, 11:09pm

In worst case there are a total of 2*50000 nos (including updates) that will be needing 10^5 * 2^6 * log2(50000) = 99901699 nodes that is well within the Memory Limit.

We have solved the problem in O( 2^6 * Q * log2(N) ) time and O( 9*10^7 ) memory

beginner_1111 · March 14, 2018, 1:57pm

@nilmadhab1 what is square free divisor?

animeshp_1993 · March 16, 2018, 10:29am

how to find F(x,L,R) in O(logN) time by querying over ordered set corresponding to x ? If I am using ordered_map , I can get iterator corresponding to L and R in O(logN) . But getting their difference will take linear time .

sumitjha4321 · March 23, 2018, 1:10am

nice approach sir +1

sarthakmanna · March 23, 2018, 9:18pm

I am still a student. Anyway, thanks @sumitjha4321

And thanks @teruel98 for pointing out the error.