A few problems to remember of GCD and LCM

Image for post
Image for post
Courtesy: appadvice.com

First of all I am going to list up these problems because I want to keep these as a note in my own way. Besides these problems will improve the idea of GCD and LCM. Hence proper understanding of these problems eventually enhance our capability to solve other problems on this topic. Here is the list of problems:

  1. GCD from 1 to N
  2. LCM from 1 to N
  3. Number of pairs with given LCM (L)
  4. Number of pairs with given LCM (L) and GCD (G)
  5. GCD of an Array
  6. LCM of an Array
  7. Number of pairs with (i, N) with GCD (D) where D|N and 1≤ i ≤ N
  8. Sum of GCD of pairs (i, N) where 1 ≤ i ≤ N (aka GCD Sum Function)
  9. Sum of LCM of pairs (i, N) where 1 ≤ i ≤ N (aka LCM Sum Function)
  10. Sum of GCD of all pairs (aka GCD Extreme)
  11. Sum of LCM of all pairs (aka LCM Extreme)

1. GCD from 1 to N

Is this really a problem to solve. We all know it’s not, nevertheless I add this to keep a problem for GCD which aligns with the title of 2nd problem “LCM from 1 to N”. Kinda savage. :P

Solution: Need to remind one property of GCD

Property 1:
GCD(a[1], a[2], ... a[n]) = GCD(GCD(a[1], a[2], ... a[n-1]), a[n])
* Here none of the integers a[i] is equal to 0

2. LCM from 1 to N

This problem is not a riddle like the previous problem “GCD from 1 to N”. It’s a genuine problem to think about how LCM is calculated of two integers A and B.

Solution: Need to remind two properties of LCM

Property 1:
Given two integer A and B, if we can prime factorize them like following:
A = p1^a1 * p2^a2 * ... pn^an
B = p1^b1 * p2^a2 * ... pn^bn
LCM = p1^max(a1, b1) * p2^max(a1, b1) * pn^max(an, bn)

3. Number of pairs with given LCM (L)

The solution I know right now maybe isn’t the best solution.

Input:
L = 12, Answer = 8

Solution:

For,
L = 12 = 2^2 * 3
Number of pairs are given below:
(1, 12)
(2, 12)
(3, 12)
(4, 12)
(6, 12)
(12, 12)
(3, 4)
(4, 6)

4. Number of pairs with given LCM (L) and GCD (G)

This problem is more easy then the previous.

Input:
L = 12, G = 2,
Output: 2
(4, 6), (2, 12)

Solution:

First of all in both numbers of a pair have to contain GCD value G. Its mandatory otherwise GCD of that pair won't be equal to value G. To understand the fact here lets prime factorize both L and G:

5. GCD of an Array

This problem is easy if we can remind the problem “GCD from 1 to N”. This problem is a directly linked to one of the GCD properties.

Input:
A = [4, 6, 10]
Output: 2

Solution: Need to remind one of the properties of GCD

Property 1:
Given two integer A and B, if we can prime factorize them like following:
A = p1^a1 * p2^a2 * ... pn^an
B = p1^b1 * p2^a2 * ... pn^bn
GCD = p1^min(a1, b1) * p2^min(a1, b1) * pn^min(an, bn)

6. LCM of an Array

This problem is a directly linked to one of the LCM property.

Input:
A = [12, 18, 75]
Output:
900

Solution: Need to remind one of the properties of LCM.

Property 1:
Given two integer A and B, if we can prime factorize them like following:
A = p1^a1 * p2^a2 * ... pn^an
B = p1^b1 * p2^a2 * ... pn^bn
LCM = p1^max(a1, b1) * p2^max(a1, b1) * pn^max(an, bn)

7. Number of pairs with (i, N) with GCD (d) where d|N and 1 ≤ i ≤ N

This problem is based on direct theorem of Euler 𝜑 function. Given an integer N and d which is divisor of N, count number of pairs (i, N) = d where 1 ≤ i ≤ N.

Input:
N = 30, D = 3
Output:
7

Solution: Since I already told it’s just a theorem based on euler 𝜑 function. Here is the theorem:

Given an integer N and d is a divisor of N, the numbers of pairs (i, N) where 1 ≤ i ≤ N and GCD(i, N) = d is 𝜑(N/d)

8. Sum of GCD of pairs (i, N) where 1 ≤ i ≤ N (aka GCD SUM Function)

Given a positive integer N, GCD SUM function is like:

Image for post
Image for post

gcdSum(N) = gcd(1, N) + gcd(2, N) + gcd(3, N) + … + gcd(N, N)

Example:

N = 6
gcdSum(6) =
gcd(1, 6) + gcd(2, 6) +
gcd(3, 6) + gcd(4, 6) +
gcd(5, 6) + gcd(6, 6) = 15

Solution:

Lets revisit how did we calculate for N = 6

I have also a personal note on this problem. You can have a look on that. GCD AND LCM SUM.

9. Sum of LCM of pairs (i, N) where 1 ≤ i ≤ N (aka LCM Sum Function)

Given a positive integer N, LCM SUM function is like:

Image for post
Image for post

First of all we have to understand the solution of GCD SUM function before going through the solution of this LCM SUM problem. Anyway this problem is hard to explain without proper mathematical notations which medium doesn’t support. So lets have a look on my personal note GCD AND LCM SUM.

You can find the code here: LCMSUM.

10. Sum of GCD of all pairs (aka GCD Extreme)

This problem is an extension of GCD SUM problem. The problem statement is very tiny which is given a positive integer N, we have to find GCD of all pairs between from 1 to N and calculate sum of them. Mathematical expression is like following:

Image for post
Image for post
Courtesy: UVA Online Judge
Input:
N = 6
Output:
16

Solution:

For N = 6, we can write:
(gcdSum(6) - 6) +
(gcdSum(5) - 5) +
(gcdSum(4) - 4) +
(gcdSum(3) - 3) +
(gcdSum(2) - 2) +
(gcdSum(1) - 1)
*gcdSum() function comes from previous problem.

NO !!!
Lets remind how we can compute multiplicative functions efficiently.
Calculate t(n) and σ(n) up to 10⁷ efficiently

Algorithm Steps:
1.
Calculate gcdSum(n) up to 4,000,000
2. At the same time in a separate array DP[] keep sum of gcdSum(n) from 1 to n using dynamic programming approach.

You can find the code here: GCD Extreme II

11. Sum of LCM of all pairs (aka LCM Extreme)

This problem is an extension of LCM SUM problem. Use the formula of LCM SUM function and DP technique.

Written by

Computer Programmer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store