How to compute sum of submatrix of a GCD matrix?

Revision en1, by tatya_bichu, 2018-02-22 13:57:18

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

Tags #matrix, gcd, pair

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English tatya_bichu 2018-02-22 14:47:09 280 (published)
en1 English tatya_bichu 2018-02-22 13:57:18 662 Initial revision (saved to drafts)