Hello
Let gcdsum[n] = gcd(1,1)+gcd(1,2)+gcd(1,3)+ ... +gcd(n,n)
Also gcdsum[n] can be evaluated using :
gcdsum[n] = n*sum(eulerphi(d)/d) for all d | n
Now to compute all gcdsum values upto n we first need to precompute
all eulerphi and then use a sieve like algorithm to make a table of
all
I guess you are referring to this problem
http://icpcres.ecs.baylor.edu/onlinejudge/external/114/11424.html , which is
also GCDEX in spoj.
gcdsum function is multiplicative, so you can calculate it from 2 to N
one-by-one.
Also, for a prime p, gcdsum[ p^k ] = (k+1).p^k - (k).p^(k-1) { I just used
