### tatya_bichu's blog

By tatya_bichu, history, 7 months ago, ,

given infinite size GCD matrix: GCD matrix is a matrix where each element S(i,j) = GCD(i,j) .Also we are given with N,M(both <=500000).You need to answer sum of all elements of matrix from (0,0) to (N,M) of the GCD matrix. Example: Given :- N=3,M=2 Solution: A 3x2 matrix have entries

gcd(1,1) gcd(1,2)
gcd(2,1) gcd(2,2)
gcd(3,1) gcd(3,2)
answer will be 1+1+1+1+2+1=7
My approach:
for sub-matrix (0,0) to (min(N,M),min(N,M)) I can calculate using GCD pairs count but how Do I get sum of remaining entries efficiently O(NlogN)?

•
• -5
•

 » 7 months ago, # |   0 This problem was discussed here, the sum can be computed in .