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 it.. after seeing it somewhere :p } , so thats it.. given a number N, break it as follows, N = (p^k) * (M) ; so, gcdsum[N] = gcdsum[p^k] * gcdsum[M] . May be subtract N from it after this. Hope you can get it working now with this idea. - AK On Tue, Jan 26, 2010 at 7:13 PM, abhijith reddy <abhijith200...@gmail.com>wrote: > 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 gcdsum . > > But can any one tell me a way to compute the gcd sum values without > computing phi . Since a table of eulerphi could be made without > computing prime numbers, but i am unable to extend this idea. > > Can any one help ? > > Thanks ! > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Anil Kishore -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.