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 <[email protected]>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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
