so Ans= Sum over i {i*n/(i,n)} Replacing i by n-i: = Sum over i {(n-i)*n/(n-i,n) } As (n-i,n)=(n,i), so adding: Ans = Sum over i {n*n/(i,n) }/2= (n*n/2){1/(i,n) } (n*n)/2 * Sum over i {1/(i,n)}
Now I have to find Sum'= Sum over i : 1/(i,n) Let (i,n)=k. so as i varies from 1 to n, k varies from 1 to n too Now next question to ask is how many elements have gcd K with n ?
it must be some element of type K*e st k*e<=n && (e,n)==1 or e<=n/K && (e,n)==1 so this is just phi(n/k) ( for k=1 , it is phi(n)+1 ) so Sum' = 1+ Sum over k from 1 to n {phi(n/k)*(1/k)} now as k | n , replace k by n/k to get Sum' = 1+ {Sum over k from 1 to n + k*phi(k) }
So final answer is = (n*n)/2 * Summation over divisor k of n {k*phi(k)}
Quantity k*phi(k) can be computed using a seive like procedure in O(nlogn) for all from 1 to n
So finally- O(nlogn) preprocessing & O(1) query time.
"so this is just phi(n/k) ( for k=1 , it is phi(n)+1 )"
Actually this is wrong, it is simply phi(n). The additional "1" comes in the very first para ::
"Replacing i by n-i: = Sum over i {(n-i)*n/(n-i,n) } As (n-i,n)=(n,i), so adding:"
You have ignored the fact that for i = n , (n,i) != (n,n-i) hence 1 is substituted for i=n; And for the remaining it is equal to n/(n,i), as you said ,for i=1 to i=(n-1) .
Lcm(i,j)= i*j/(i,j)
ReplyDeleteso
Ans= Sum over i {i*n/(i,n)}
Replacing i by n-i:
= Sum over i {(n-i)*n/(n-i,n) }
As (n-i,n)=(n,i), so adding:
Ans = Sum over i {n*n/(i,n) }/2= (n*n/2){1/(i,n) }
(n*n)/2 * Sum over i {1/(i,n)}
Now I have to find Sum'= Sum over i : 1/(i,n)
Let (i,n)=k. so as i varies from 1 to n, k varies from 1 to n too
Now next question to ask is how many elements have gcd K with n ?
it must be some element of type K*e st
k*e<=n && (e,n)==1
or e<=n/K && (e,n)==1
so this is just phi(n/k) ( for k=1 , it is phi(n)+1 )
so
Sum' = 1+ Sum over k from 1 to n {phi(n/k)*(1/k)}
now as k | n , replace k by n/k
to get
Sum' = 1+ {Sum over k from 1 to n + k*phi(k) }
So final answer is
= (n*n)/2 * Summation over divisor k of n {k*phi(k)}
Quantity k*phi(k) can be computed using a seive like procedure in O(nlogn) for all from 1 to n
So finally- O(nlogn) preprocessing & O(1) query time.
/*
ReplyDeleteSo final answer is
= (n*n)/2 * Summation over divisor k of n {k*phi(k)}}
*/
I think ,
it'll be n/2 * Summation over divisor k of {k*phi(k)}}
because 1/k becomes k/n not k.
BTW pretty cool explanation... :)
@Ritesh-
ReplyDeleteThanks for pointing out. :)
I had scribbled down the solution in hurry.
/*
ReplyDeletek*e<=n && (e,n)==1
or e<=n/K && (e,n)==1
so this is just phi(n/k) ( for k=1 , it is phi(n)+1 )
*/
what extra element should we add. I dont get it.
"so this is just phi(n/k) ( for k=1 , it is phi(n)+1 )"
ReplyDeleteActually this is wrong, it is simply phi(n).
The additional "1" comes in the very first para ::
"Replacing i by n-i:
= Sum over i {(n-i)*n/(n-i,n) }
As (n-i,n)=(n,i), so adding:"
You have ignored the fact that for i = n , (n,i) != (n,n-i)
hence 1 is substituted for i=n; And for the remaining it is equal to n/(n,i), as you said ,for i=1 to i=(n-1) .