{"id":839,"date":"2020-07-01T09:40:56","date_gmt":"2020-07-01T09:40:56","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=839"},"modified":"2022-03-25T10:45:21","modified_gmt":"2022-03-25T10:45:21","slug":"one-more-gcd-sum","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/one-more-gcd-sum\/","title":{"rendered":"One more GCD sum"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Mathematics<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n

Calculate the sum for a given number n<\/code>:<\/p>\n

<\/p>\n

<\/strong><\/u><\/a><\/p>\n

Solving Approach :<\/h3>\n

Bruteforce Approach<\/strong>:<\/p>\n

\n

1) We can use a double loop to count sum for a given value of n<\/code>, where a loop also occurs inside two loops to find gcd(i,j)<\/code>.
\n2) The Above approach use three loops to solve the given problem. So it takes a total of O(n\u00b3)<\/code> time complexity which is highly inefficient for given constraints, so we add some maths magic to it and solve it faster. <\/p>\n<\/blockquote>\n

Efficient Approach<\/strong>:<\/p>\n

\n

1) Let gcd(i,j) = d<\/code>, where d can go from 1<\/code> to n<\/code>. If gcd(i,j)<\/code> is d<\/code>, i<\/code> and j<\/code> can be represented as some multiple of d<\/code>, let i=k*d<\/code> and j=l*d<\/code>, where k<\/code><l<\/code> because i<\/code> 2) Our summation equation is , from above step we can see it becomes,<\/p>\n

=> (i=k*d<\/code> and j=l*d)<\/code> <\/p>\n

=> (gcd(i,j) = d)<\/code> <\/p>\n

=> k*l<\/code> <\/p>\n

3) Now, we have one summation for one value of d<\/code> ranging from 1<\/code> to N<\/code>, internally we have (k*l)<\/code> summation over all pairs where l>k<\/code> and gcd(l,k)=1<\/code>. Total number of pairs such that gcd(n,k)=1<\/code> where k<\/code> lies between 1<\/code> and n<\/code> can be found by using Euler Totient Function<\/a>. An array phi<\/code> will be maintained for such values.
\n4) Also we know gcd(l,k) = gcd(l,l-k)<\/code> where l>k<\/code> and l>l-k<\/code>, so in above recieved equation we can change value of k<\/code> to l-k<\/code>, as they both will have same gcd()<\/code>, so sum(k*l) = sum(l*(l-k)))<\/code>.
\n5) We can make it further easy, as sum(kl) = sum(<\/code> which is also equal to because we still need to find summation over gcd(l,k)=1<\/code>, where `k
\n6) Now we have only l<\/code> as variable to cound ranging from 2<\/code> to (<\/code>)<\/code> and d<\/code> lies in range 1<\/code> to n<\/code>, which can be find in O(<\/code>)<\/code> time for a given value of n<\/code>.
\n7) However we can calculate for all n = 2 to 2000000 using the below pseudocode:<\/p>\n<\/blockquote>\n

Calculate phi() for all values between 1 to max range of numbers.\n    phi(n) returns the total number of values from 1 to n which have gcd() with n as 1.\n\nCalculate (l*l*phi(l))\/2 for all values of 2 to n with double summation as asked in the problem.<\/code><\/pre>\n
\n
8) Note:<\/em><\/strong> Don’t forget to take modulo to avoid overflow.<\/p>\n<\/blockquote>\n
Example<\/h3>\n
\n
    \n
  • Lets assume N<\/code> to be 10<\/code>, the phi<\/code> table for it would be:    <\/li>\n<\/ul>\n<\/blockquote>\n\n\n\n\n\n
    N<\/th>\n1<\/th>\n2<\/th>\n3<\/th>\n4<\/th>\n5<\/th>\n6<\/th>\n7<\/th>\n8<\/th>\n9<\/th>\n10<\/th>\n<\/tr>\n<\/thead>\n
    Value<\/td>\n1<\/td>\n1<\/td>\n2<\/td>\n2<\/td>\n4<\/td>\n2<\/td>\n7<\/td>\n2<\/td>\n6<\/td>\n4<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    \n
      \n
    • \n
      Where, phi(8) will be 2<\/code> because, 3<\/code> and 5<\/code> both have gcd()<\/code> 1<\/code> with 8<\/code>.<\/p>\n<\/li>\n
    • \n
      Now , we have found the value of phi(k).<\/p>\n<\/li>\n
    • \n
      We find sunmmation of all values from 1<\/code> to 10<\/code> with derived formula.  <\/p>\n<\/li>\n
    • \n
      Hence resultant array would be:   <\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n\n\n\n\n\n
      N<\/th>\n1<\/th>\n2<\/th>\n3<\/th>\n4<\/th>\n5<\/th>\n6<\/th>\n7<\/th>\n8<\/th>\n9<\/th>\n10<\/th>\n<\/tr>\n<\/thead>\n
      Value<\/td>\n0<\/td>\n2<\/td>\n11<\/td>\n29<\/td>\n79<\/td>\n126<\/td>\n273<\/td>\n419<\/td>\n671<\/td>\n923<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
      \n
        \n
      • Hence, gcd sum of 10<\/code> will be 923<\/code>. <\/li>\n<\/ul>\n<\/blockquote>\n
        Solutions<\/h3>\n\t\t\t\t\t\t