Please read the new rule regarding the restriction on the use of AI tools. ×

TLE with an O(n sqrt(n))

Revision en1, by proofbycontradiction, 2018-12-06 10:50:51

I was solving this interesting number-theory + trees problem. And I came up with an solution where n ≤ 200000.

My idea is that the answer for every node will either be a factor of the root or be a factor of the number itself, and only these about values need to be tested.

The solution in the e

Tags c++, number theory, trees, optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English proofbycontradiction 2018-12-06 11:06:47 214 (published)
en2 English proofbycontradiction 2018-12-06 10:57:24 814
en1 English proofbycontradiction 2018-12-06 10:50:51 411 Initial revision (saved to drafts)