Last Updated: 23 Apr, 2021

GCD Sum

Hard

Asked in companies

Solve now

Problem statement

Consider all numbers from 1 to ‘N’, your task is to find the sum of gcd of all pairs (i, j) such that 1 <= i < j <= N.

For example for N = 3, all pairs are { (1, 2), (1, 3), (2, 3) }.

Note :

Gcd of two numbers (X, Y) is defined as the largest integer that divides both ‘X’ and ‘Y’.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases to be run. The 'T' test cases follow.

The first line of each test case contains an integer ‘N’ representing the given integer.

Output Format :

For each test case, print an integer representing the sum of gcd of all pairs of numbers from 1 to ‘N’.

The output of each test case will be printed in a separate line.

Note :

You do not need to input or print anything, and it has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 5
1 <= 'N' <= 5000

Time Limit: 1sec

Solve now

Approaches

01 Approach

For a given ‘N’, we can iterate over all possible pairs and find the resulting sum by adding them.

Algorithm:

Let the given integer be ‘N’.
Declare a variable ‘answer’ to store the gcd sum of all pairs.
Run a loop from ‘i’ = 1 to ‘N’.
- Run a loop from ‘j’ = i + 1 to ‘N’
  - Increase ‘answer’ by gcd of ‘i’ and ‘j’, i.e. do ‘answer’ += gcd(i, j).
Return ‘answer’

Solve now

02 Approach

We need to find the sum of all pairs (i, j) where ( 1 <= ‘i’, ‘j’ <= ‘N’ and ‘j’ > ‘i’ ). Let define a function - f(x) that gives the sum of gcd of all pairs (i, x), such that ‘i’ <= ‘x’. Then the answer will be f(1) + f(2) + f(3) + f(4) … f(N) - N * (N + 1) / 2, as we need to subtract pairs with the same value i.e. gcd (x, x). Now the problem is how we could find f(x) efficiently. Here we can use Euler's totient function, which gives the count of coprime numbers less than the given number. Now f(x) for any integer ‘x’ can be found as a summation of (d * phi( ‘x’ / d) ), for all ‘d’ that is a divisor of ‘x’, where phi () is the Euler's totient function. We can precompute phi() for all the integers and then compute f(x) for all ‘x’ less than ‘N’ using the sieve method instead of iterating over all divisors for all ‘x’. Finally we can return the sum of f(1) to f(N) - N * (N + 1) / 2.

Algorithm:

Let the given integer be ‘N’.
Declare a variable ‘answer’ to store the gcd sum of all pairs.
Precalculate Euler's totient function in an array say ‘phi’ for each 'i' from 1 to ‘N’.
Declare an array of size 'N' say ‘pre’ to store the value of f(x) for each ‘x’ from 1 to ‘N’.
Declare a function say ‘preCompute’ to calculate the values of ‘pre’.
Call ‘preCompute’ function.
Run a loop from ‘i’ = 1 to ‘N’.
- Increase ‘answer’ by pre[i], i.e. do ‘answer’ += ‘pre[i]’.
- Subtract ‘i’ from ‘answer’, as we don’t want gcd(i, i);
Return ‘answer’

Description of ‘preCompute’ function

The function will calculate f(x) for each ‘x’ from 1 to ‘N’ using the sieve method.

The function will take one parameter:

‘N’: an integer up to which the ‘f(x)’ will be calculated.

‘phi’: an array of Euler's totient function value for each 'i' from 1 to ‘N’

array preCompute ( N, phi):

Run a loop from i = 0 to ‘N’.
- Run a loop over all integers ‘j’ < ‘N’ such that ‘i’ divides ‘j’.
  - Increase pre[j] by (i * phi [j / i]), i.e. do ‘pre[j]’ += ‘i’ * ( ‘phi [j / i]’).

Solve now