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:
1;
1, 2;
1, 1, 3;
1, 2, 1, 4;
1, 1, 1, 1, 5;
1, 2, 3, 2, 1, 6; ... these values keeps on repeating for each column starting from 1 to M But still can't figure out how to get sum of