Number Theory Problem from UAP NCPC 2016 Contest

Revision en2, by Tobby_And_Friends, 2016-09-29 14:59:42

UVA 13083

Name: Yet another GCDSUM

Link: https://uva.onlinejudge.org/external/130/13083.pdf

I did get the idea that I'll initially compute all the divisors of N using prime factorization & backtracking but I'm stuck in how to compute the gcd of the divisor pairs with a better complexity than O(n^2). Any help is really appreciated.

Tags number theory, uva, gcd

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Tobby_And_Friends 2016-09-29 14:59:42 4
en1 English Tobby_And_Friends 2016-09-29 14:59:18 385 Initial revision (published)