# A few problems to remember of GCD and LCM

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, a, ... a[n]) = GCD(GCD(a, a, ... a[n-1]), a[n])* Here none of the integers a[i] is equal to 0Now suppose,N = 2, GCD(1, 2) = 1N = 3, GCD(GCD(1, 2), 3) = 1N = 4, GCD(GCD(1, 2, 3), 4) = 1Well, it's always 1.Complexity: O(1)`

# 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^anB = p1^b1 * p2^a2 * ... pn^bnLCM = p1^max(a1, b1) * p2^max(a1, b1) * pn^max(an, bn)Property 2:LCM(a, a, ... a[n]) = LCM(LCM(a, a, ... a[n-1]), a[n])Now for N = 10, factorization from 1 to 10:1  = 12  = 23  = 34  = 2^25  = 56  = 2 * 37  = 78  = 2^39  = 3^210 = 2 * 5LCM = 2^3 * 3^2 * 5 * 7So, LCM will be multiplication of prime exponents. For each prime (p) up to N, we have to find largest exponent (a). How to do that? Divide N by prime p until it becomes 0.Algorithm Steps:#1. Generate primes up to N using optimized sieve which is pre-calculation.#2. In a separate array memo[] calculate product of primes dynamically for up to each prime which is also pre-calculation.#3. Then for an input N, for primes up to sqrt(N) find exponent (a) of that prime (p) and multiply p^(a-1) this to final answer. For primes larger than sqrt(N) use memo[] array to find products of primes exist up to N and at last multiply this to final answer.Complexity: !!!`

# 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 * 3Number of pairs are given below:(1, 12)(2, 12)(3, 12)(4, 12)(6, 12)(12, 12)(3, 4)(4, 6)Notice, all divisors of 12 along with 12 is a valid pair. Plus there are additional 2 pairs which is made among the divisors. So the solution is like count number of divisors plus check LCM of each pair of the divisors.`

# 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)Input:L = 360, G = 2,Output: 4* Find the exact pairs by yourself`

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:L = 360 = 2^3 * 3^2 * 5G =   2 = 2^1Lets construct pair manually,A = 2^1 * X (some prime factors exponent from factorization of L)B = 2^1 * Y (some prime factors exponent from factorization of L)Now the problem turns into finding (X,Y) pairs from prime factorization of L/G:L/G = 2^2 * 3^2 * 5Note that gcd of (X,Y) must be 1 that means there will no common factors between them. There are 3 prime factor exponent terms. We can put them either in A or B. For example, we can put 2^2 in A, then others in B. Now the problem turns into combination problems. How many ways we can put 3 items into 2 positions.= C(3, 0) + C(3, 1) + C(3, 2) + C(3, 3) / 2= 2^3 / 2So finally, If L/G has k unique prime factors, answer will be (2^k) / 2.Algorithm Steps:1. Pre calculate primes using sieve.2. Factorize L/G to get number of distinct prime numbers.3. Calculate (2^k) / 2.`

# 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: 2Input:A = [3, 6, 12]Output: 3`

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^anB = p1^b1 * p2^a2 * ... pn^bnGCD = p1^min(a1, b1) * p2^min(a1, b1) * pn^min(an, bn)First intuition is if there is any 2 consecutive integers, GCD will be 1 as we have seen this in the previous problem.Second intuition is if GCD isn't equal to 1, its maximum value will be the minimum value of the array, because GCD of number A and B can't be more than min(A, B).Prime factorization will explain the fact here:Suppose A = [6, 9, 15];6  = 2^1 * 3^19  = 3^215 = 3^5;Here minimum value is 6, so we have to compare factors of 6 with other integers and take minimum of them and construct result.Algorithm Steps:1. Find minimum integer (M) with O(n) time2. Prime factorize M3. Traverse the array again and check how much of the prime factorization available in an element A[i]. Take the common part to construct result.`

# 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^anB = p1^b1 * p2^a2 * ... pn^bnLCM = p1^max(a1, b1) * p2^max(a1, b1) * pn^max(an, bn)Algorithm Steps:1. Pre-calculate primes using sieve.2. Take a map maxExponent that keeps max exponent of primes appeared. Like, if prime 2 has max exponent 3, maxExponent = 33. Traverse array to factorize each element and update max exponent for each prime factor.4. Traverse maxExponent array. If maxExponent[i] > 0, multiply i^maxExponent[i] into the result.`

# 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 = 3Output:7Explanation:GCD(3, 30)  = 3GCD(9, 30)  = 3GCD(12, 30) = 3GCD(18, 30) = 3GCD(21, 30) = 3GCD(24, 30) = 3GCD(27, 30) = 3`

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:

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

Example:

`N = 6gcdSum(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 = 6gcdSum(6) =gcd(1, 6) = 1gcd(2, 6) = 2gcd(3, 6) = 3gcd(4, 6) = 2gcd(5, 6) = 1gcd(6, 6) = 6Sum = 15Notice calculating gcd of each pair (i, N) gcd will be always divisors of N. For N, divisors are 1, 2, 3, 6Now think in reverse way, for each divisor how many pairs (i, N) available. Well, not so easy to answer for a composite number but this is what we have to find eventually.When N is a prime: gcdSum(p)====================================================================When N is a prime p, all the pairs except the pair (p, p) is has gcd value 1. For example, N = 5gcd(1, 5) = 1gcd(2, 5) = 1gcd(3, 5) = 1gcd(4, 5) = 1gcd(5, 5) = 5So, gcdSum(p) = (p-1) + p = 2p - 1;When N is power of a prime: gcdSum(p^a)====================================================================Lets illustrate an example first, N = 27 = 3^3gcd(1, 3^3) = 1gcd(2, 3^3) = 1gcd(3, 3^3) = 3...gcd(4, 3^3) = 1gcd(5, 3^3) = 1gcd(6, 3^3) = 3...gcd(3^2, 3^3) = 3^2...gcd(12, 3^3) = 3gcd(15, 3^3) = 3...gcd(3^3, 3^3) = 3^3Notice the gcd of (i, p^a). As you already noticed gcd value will be divisors of p^1 so the values will be 1, p, p^2, ... p^a. Now we can think in reverse way, for each divisor how many pairs (i, N) exist.Remind previous problem, Number of pairs with (i, N) with GCD (d) where d|N and 1 ≤ i ≤ N is 𝜑(N/d).Now we can calculate gcdSum(p^a) like this:For d = 1,   𝜑(p^a / 1) * 1For d = p,   𝜑(p^a / p) * pFor d = p^2, 𝜑(p^a / p^2) * p^2...For d = p^a, 𝜑(p^a / p^a) * p^a--------------------------------------gcdSum(p^a)= 𝜑(p^a / 1) * 1 + 𝜑(p^a / p) * p + 𝜑(p^a / p^2) * p^2 + ... + 𝜑(p^a / p^a) * p^a= 𝜑(p^a) + 𝜑(p^(a-1)) * p + 𝜑(p^(a-2)) * p^2 + ... + p^aWe know, 𝜑(p^a) = p^a - p^(a-1)gcdSum(p^a) =p^a - p^(a-1) + p^a - p^(a-1) + p^a - p^(a-1) + ... p^agcdSum(p^a) = a * (p^a - p^(a-1)) + p^agcdSum(p^a) = (a + 1) * p^a - p^(a-1)When N is a composite integer:====================================================================If N is prime factorized like following:N = p1^a1 * p2^a2 * p2^a2 * ... * pN^aNgcdSum(N) = gcdSum(p1^a1) * gcdSum(p2^a2) * ... * gcdSum(pN^aN)where gcdSum(pi^ai) = (ai + 1) * pi^a - pi^(ai-1)*It can be proved that gcdSum(N) is multiplicative like euler 𝜑 function.`

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:

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:

`Input:N = 6Output:16Explanation:GCD(1,2) + GCD(1,3) + GCD(1,4) + GCD(1,5) + GCD(1,6) =GCD(2,3) + GCD(2,4) + GCD(2,5) + GCD(2,6) =GCD(3,4) + GCD(3,5) + GCD(3,6) =GCD(4,5) + GCD(4,6) =GCD(5,6) =Result:`

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.In the problem GCD-Extreme(II) in UVA OJ Suppose highest value of N is 4,000,000. So need to pre-calculate up to 4,000,000.But still there is a TLE issue.1. How do we calculate gcdSum(i) for each i where 1 <= i <= 4*10^6?2. Do we prime factorize each i seperately and calculate gcdSum(i)?`

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,0002. 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