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 <kumar0...@gmail.com> 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 algogeeks@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.