Given an integer N, the task is to count the total number of ordered pairs such that the LCM of each pair is equal to N.
Examples:
Input: N = 6
Output: 9
Explanation:
Pairs with LCM equal to N(= 6) are {(1, 6), (2, 6), (2, 3), (3, 6), (6, 6), (6, 3), (3, 2), (6, 2), (6, 1)}
Therefore, the output is 9.Input: N = 36
Output: 25
Brute Force Approach:
A brute force approach to solve this problem would be to consider all possible pairs of integers (a,b) such that 1 <= a,b <= N, and then check if their LCM is equal to N. If it is, then count it as a valid pair.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to count the number of// ordered pairs with given LCMint CtOrderedPairs(int N){ int count = 1; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (i != j && i * j / __gcd(i, j) == N) { // Increment the count count++; } } } return count;}// Driver Codeint main(){ int N = 6; cout << CtOrderedPairs(N); return 0;} |
Python3
# Import the gcd function from the math modulefrom math import gcd# Function to count the number of ordered pairs with given LCMdef count_ordered_pairs(N): count = 1 for i in range(1, N+1): for j in range(1, N+1): if i != j and i*j // gcd(i, j) == N: count += 1 return count# Driver codeN = 6print(count_ordered_pairs(N)) |
C#
using System;public class Program { // Function to count the number of // ordered pairs with given LCM public static int CtOrderedPairs(int N) { int count = 1; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (i != j && i * j / GCD(i, j) == N) { count++; } } } return count; // To avoid counting same pairs twice } // Function to calculate GCD of two numbers public static int GCD(int a, int b) { if (b == 0) return a; return GCD(b, a % b); } // Driver Code public static void Main() { int N = 6; Console.WriteLine(CtOrderedPairs(N)); }} |
Java
import java.util.*;public class Main { // Function to count the number of // ordered pairs with given LCM static int ctOrderedPairs(int N) { int count = 1; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (i != j && i * j / gcd(i, j) == N) { count++; } } } return count; // To avoid counting same pairs twice } // Function to calculate GCD using Euclidean algorithm static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Driver Code public static void main(String[] args) { int N = 6; System.out.println(ctOrderedPairs(N)); }} |
Javascript
// Function to count the number of ordered pairs with given LCMfunction count_ordered_pairs(N) {let count = 1;for (let i = 1; i <= N; i++) {for (let j = 1; j <= N; j++) {if (i !== j && (i*j) / gcd(i, j) === N) {count += 1;}}}return count;}// Function to calculate GCD using Euclidean algorithmfunction gcd(a, b) {if (b === 0) {return a;}return gcd(b, a % b);}// Driver codeconst N = 6;console.log(count_ordered_pairs(N)); |
Output
9
Time Complexity: O(N^2)
Auxiliary Space: O(1)
Approach: The problem can be solved based on the following observations:
Consider an ordered pair(X, Y).
X = P1a1 * P2a2 * P3a3 *…..* Pnan
Y = P1b1 * P2b2 * P3b3 *…..* Pnbn
Here, P1, P2, ….., Pn are prime factors of X and Y.
LCM(X, Y) = P1max(a1, b1) * P2max(a2, b2) *……….*Pnmax(an, bn)
Therefore, LCM(X, Y) = N = P1m1 * P2m2 * P3m3 *…..* PnmnTherefore, total number of ordered pairs (X, Y)
= [{(m1 + 1)2 – m12} * {(m2 + 1)2 – m22} * ……* {(mn + 1)2 – mn2} ]
= (2*m1+1) * (2*m2+1) * (2*m3+1) * ……..* (2*mn+1).
Follow the steps below to solve the problem:
- Initialize a variable, say, countPower, to store the power of all prime factors of N.
- Calculate the power of all prime factors of N.
- Finally, print the count of ordered pairs(X, Y) using the aforementioned formula.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// ordered pairs with given LCMint CtOrderedPairs(int N){ // Stores count of // ordered pairs int res = 1; // Calculate power of all // prime factors of N for (int i = 2; i * i <= N; i++) { // Store the power of // prime factors int countPower = 0; while (N % i == 0) { countPower++; N /= i; } res = res * (2 * countPower + 1); } if (N > 1) { res = res * (2 * 1 + 1); } return res;}// Driver Codeint main(){ int N = 36; cout << CtOrderedPairs(N);} |
Java
// Java program to implement// the above approachclass GFG{ // Function to count the number of// ordered pairs with given LCMstatic int CtOrderedPairs(int N){ // Stores count of // ordered pairs int res = 1; // Calculate power of all // prime factors of N for(int i = 2; i * i <= N; i++) { // Store the power of // prime factors int countPower = 0; while (N % i == 0) { countPower++; N /= i; } res = res * (2 * countPower + 1); } if (N > 1) { res = res * (2 * 1 + 1); } return res;}// Driver Codepublic static void main(String[] args){ int N = 36; System.out.println(CtOrderedPairs(N));}}// This code is contributed by aimformohan |
Python3
# Python3 program to implement# the above approach # Function to count the number of# ordered pairs with given LCMdef CtOrderedPairs(N): # Stores count of # ordered pairs res = 1 # Calculate power of all # prime factors of N i = 2 while(i * i <= N): # Store the power of # prime factors countPower = 0 while (N % i == 0): countPower += 1 N //= i res = res * (2 * countPower + 1) i += 1 if (N > 1): res = res * (2 * 1 + 1) return res# Driver CodeN = 36print(CtOrderedPairs(N))# This code is contributed by code_hunt |
C#
// C# program to implement// the above approachusing System; class GFG{ // Function to count the number of// ordered pairs with given LCMstatic int CtOrderedPairs(int N){ // Stores count of // ordered pairs int res = 1; // Calculate power of all // prime factors of N for(int i = 2; i * i <= N; i++) { // Store the power of // prime factors int countPower = 0; while (N % i == 0) { countPower++; N /= i; } res = res * (2 * countPower + 1); } if (N > 1) { res = res * (2 * 1 + 1); } return res;} // Driver Codepublic static void Main(){ int N = 36; Console.WriteLine(CtOrderedPairs(N));}}// This code is contributed by code_hunt |
Javascript
<script>// Javascript program to implement// the above approach// Function to count the number of// ordered pairs with given LCMfunction CtOrderedPairs(N){ // Stores count of // ordered pairs let res = 1; // Calculate power of all // prime factors of N for(let i = 2; i * i <= N; i++) { // Store the power of // prime factors let countPower = 0; while (N % i == 0) { countPower++; N /= i; } res = res * (2 * countPower + 1); } if (N > 1) { res = res * (2 * 1 + 1); } return res;}// Driver Code let N = 36; document.write(CtOrderedPairs(N)); </script> |
Output
25
Time Complexity: O(√N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
