the required sum is:
F(n) = sum({lcm(x,y)|1<=x<y<=n})
= sum({lcm(x,y)|1<=x<=n, 1<=y<=n, x#y})/2
=(sum({lcm(x,y)|1<=x<=n, 1<=y<=n}) - n(n+1)/2)/2
=(sum({sum({lcm(x,y)|1<=x<=n, 1<=y<=n, gcd(x,y)=d}) | 1<=d<=n}) -
n(n+1)/2)/2
let f(n) = sum({lcm(x,y)|x<=n, y<=n, gcd(x,y)=1})
for gcd(x,y)=d, let x'= x/d, y' = y/d, then (x',y') = 1
sum({lcm(x,y)|x<=n, y<=n, lcm(x,y)=d})
= sum({lcm(x'd,y'd)|x'd<=n, y'd<=n, lcm(x'd,y'd)=d})
= d*sum({lcm(x',y')|x'<=[n/d], y'<=[n/d], lcm(x',y')=1})
= d*f([n/d])
so F(n) = (sum({d*f([n/d]) | 1<=d<=n}) - n(n+1)/2)/2
f(n) = sum({lcm(x,y)|1<=x<=n, 1<=y<=n, gcd(x,y)=1}) = sum({xy|1<=x<=n,
1<=y<=n, gcd(x,y)=1})
let G(n) = sum({xy|1<=x<=n, 1<=y<=n})
then G(n) = sum({sum({xy|1<=x<=n, 1<=y<=n, gcd(x,y)=d})|1<=d<=n})
again for gcd(x,y)=d let x'= x/d, y' = y/d, then (x',y') = 1
sum({xy|1<=x<=n, 1<=y<=n, gcd(x,y)=d})
= sum({x'd*y'd|1<=x'd<=n, 1<=y'd<=n, gcd(x'd,y'd)=d})
= d^2*sum({x'y'|1<=x'<=[n/d], 1<=y'<=[n/d], gcd(x',y')=1})
= d^2*f([n/d])
so G(n) = sum({d^2*f([n/d])|1<=d<=n})
as G(n) = sum({xy|1<=x<=n, 1<=y<=n}) = (1+2+...+n)*(1+2+...+n) = n^2*(n
+1)^2/4
f(n) = G(n) - sum({d^2*f([n/d])|2<=d<=n})
= n^2*(n+1)^2/4 - sum({d^2*f([n/d])|2<=d<=n})
Using this sieve to calculate f(n), then use f(n) to calculate F(n).
The direct implementation is O(n^2) time and O(n) space, and can be
optimized to O(n^1.5) time.
(break the interval by n^(1/2) into 2 parts, and use different method
in each interval)
On Dec 18, 8:04 pm, arun kumar <[email protected]> wrote:
> long long function( int n ) {
> long long res = 0;
> for( int i = 1; i <= n; i++ )
> for( int j = i+1; j <= n; j++ )
> res+=lcm(i,j);
> return res;
>
> }
>
> N<=5*10^6 and TestCases<=25000.. TimeLimit=5s
> Can anyone give hints to solve this ?
> Thanks in advance !
--
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.
