Please subscribe to the official Codeforces channel in Telegram via the link: ×

tatya_bichu's blog

By tatya_bichu, history, 10 months ago, In English,

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)?

  • Vote: I like it  
  • -5
  • Vote: I do not like it  

10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem was discussed here, the sum can be computed in .