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.