Hard Problems on GCD and LCM
- Stein’s Algorithm for finding GCD
- Largest subsequence having GCD greater than 1
- Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B
- Smallest number divisible by n and has at-least k trailing zeros
- Array with GCD of any of its subset belongs to the given array
- Find pair with maximum GCD in an array
- First N natural can be divided into two sets with given difference and co-prime sums
- Series with largest GCD and sum equals to n
- Maximum sum of distinct numbers with LCM as N
- Queries for GCD of all numbers of an array except elements in a given range
- Summation of GCD of all the pairs up to N
- Count number of subsets of a set with GCD equal to a given number
- Check if elements of array can be made equal by multiplying given prime numbers
Quick Links:
Mathematical Algorithms | GCD & LCM
Greatest Common Divisor (GCD):
The GCD of two numbers is defined as the largest integer that divides both integers without any remainder. It is also termed as the HCF (Highest Common Factor). GCD of an array is the integer that divides all the elements of the array without leaving any remainder.
GCD of two numbers may be calculated using the following ways:
- Prime Factorization
- Divisions by Prime
- Euclidean Algorithm
Least Common Multiple (LCM):
The LCM of two numbers is defined as the smallest integer which is a multiple of both integers. LCM of an array is the smallest possible integer that is multiple of all the elements of the array.
Below are some process to find LCm of two numbers:
- Prime Factorization
- Divisions by Prime
- Using the relation between GCD and LCM
Relation between GCD and LCM:
Consider two integers a and b and their GCD be gcd(a, b) and LCM be lcm(a, b) . Therefore,
a * b = gcd(a, b) * lcm(a, b)