Given a number N, the task is to find the number of pairs (a, b) in the range [1, N] such that their LCM is not equal to their product, i.e. LCM(a, b) != (a*b) and (b > a). There can be multiple queries to answer.
Examples:
Input: Q[] = {5}
Output: 1
Explanation:
The pair from 1 to 5 is (2, 4)
Input: Q[] = {5, 7}
Output: 1, 4
Explanation:
The pair from 1 to 5 is (2, 4)
The pairs from 1 to 7 are (2, 4), (2, 6), (3, 6), (4, 6)
Approach: The idea is to use Euler’s Totient Function.
1. Find the total number of pairs that can be formed using numbers from 1 to N. The number of pairs formed is equal to (N * (N – 1)) / 2.
2. For each integer i ? N, using Euler’s Totient Function find all such pairs which are co-prime with i and store them in the array.
Example:
arr[10] = 10 * (1-1/2) * (1-1/5)
= 4
3.
4. Now build the prefix sum table which stores the sum of all phi(i) for all i between 1 to N. Using this, we can answer each query in O(1) time.
5. Finally, the answer for any i ? N is given by the difference between the total number of pairs formed and pref[i].
Below is the implementation of the given approach:
C++
// C++ program to find the count of pairs// from 1 to N such that their LCM// is not equal to their product#include <bits/stdc++.h>using namespace std;#define N 100005// To store Euler's Totient Functionint phi[N];// To store prefix sum tableint pref[N];// Compute Totients of all numbers// smaller than or equal to Nvoid precompute(){ // Make phi[1]=0 since 1 cannot form any pair phi[1] = 0; // Initialise all remaining phi[] with i for (int i = 2; i < N; i++) phi[i] = i; // Compute remaining phi for (int p = 2; p < N; p++) { // If phi[p] is not computed already, // then number p is prime if (phi[p] == p) { // phi of prime number is p-1 phi[p] = p - 1; // Update phi of all multiples of p for (int i = 2 * p; i < N; i += p) { // Add the contribution of p // to its multiple i by multiplying // it with (1 - 1/p) phi[i] = (phi[i] / p) * (p - 1); } } }}// Function to store prefix sum tablevoid prefix(){ // Prefix Sum of all Euler's Totient Values for (int i = 1; i < N; i++) pref[i] = pref[i - 1] + phi[i];}void find_pairs(int n){ // Total number of pairs that can be formed int total = (n * (n - 1)) / 2; int ans = total - pref[n]; cout << "Number of pairs from 1 to " << n << " are " << ans << endl;}// Driver Codeint main(){ // Function call to compute all phi precompute(); // Function call to store all prefix sum prefix(); int q[] = { 5, 7 }; int n = sizeof(q) / sizeof(q[0]); for (int i = 0; i < n; i++) { find_pairs(q[i]); } return 0;} |
Java
// Java program to find the count of pairs// from 1 to N such that their LCM// is not equal to their productclass GFG{static final int N = 100005;// To store Euler's Totient Functionstatic int []phi = new int[N];// To store prefix sum tablestatic int []pref = new int[N];// Compute Totients of all numbers// smaller than or equal to Nstatic void precompute(){ // Make phi[1] = 0 since 1 cannot form any pair phi[1] = 0; // Initialise all remaining phi[] with i for (int i = 2; i < N; i++) phi[i] = i; // Compute remaining phi for (int p = 2; p < N; p++) { // If phi[p] is not computed already, // then number p is prime if (phi[p] == p) { // phi of prime number is p-1 phi[p] = p - 1; // Update phi of all multiples of p for (int i = 2 * p; i < N; i += p) { // Add the contribution of p // to its multiple i by multiplying // it with (1 - 1/p) phi[i] = (phi[i] / p) * (p - 1); } } }}// Function to store prefix sum tablestatic void prefix(){ // Prefix Sum of all Euler's Totient Values for (int i = 1; i < N; i++) pref[i] = pref[i - 1] + phi[i];}static void find_pairs(int n){ // Total number of pairs that can be formed int total = (n * (n - 1)) / 2; int ans = total - pref[n]; System.out.print("Number of pairs from 1 to " + n + " are " + ans +"\n");}// Driver Codepublic static void main(String[] args){ // Function call to compute all phi precompute(); // Function call to store all prefix sum prefix(); int q[] = { 5, 7 }; int n = q.length; for (int i = 0; i < n; i++) { find_pairs(q[i]); }}}// This code contributed by Rajput-Ji |
Python3
# Python 3 program to find the count of pairs# from 1 to N such that their LCM# is not equal to their productN = 100005# To store Euler's Totient Functionphi = [0 for i in range(N)]# To store prefix sum tablepref = [0 for i in range(N)]# Compute Totients of all numbers# smaller than or equal to Ndef precompute(): # Make phi[1]=0 since 1 cannot form any pair phi[1] = 0 # Initialise all remaining phi[] with i for i in range(2, N, 1): phi[i] = i # Compute remaining phi for p in range(2,N): # If phi[p] is not computed already, # then number p is prime if (phi[p] == p): # phi of prime number is p-1 phi[p] = p - 1 # Update phi of all multiples of p for i in range(2*p, N, p): # Add the contribution of p # to its multiple i by multiplying # it with (1 - 1/p) phi[i] = (phi[i] // p) * (p - 1)# Function to store prefix sum tabledef prefix(): # Prefix Sum of all Euler's Totient Values for i in range(1, N, 1): pref[i] = pref[i - 1] + phi[i]def find_pairs(n): # Total number of pairs that can be formed total = (n * (n - 1)) // 2 ans = total - pref[n] print("Number of pairs from 1 to",n,"are",ans)# Driver Codeif __name__ == '__main__': # Function call to compute all phi precompute() # Function call to store all prefix sum prefix() q = [5, 7] n = len(q) for i in range(n): find_pairs(q[i]) # This code is contributed by Surendra_Gangwar |
C#
// C# program to find the count of pairs// from 1 to N such that their LCM// is not equal to their productusing System;class GFG{static readonly int N = 100005;// To store Euler's Totient Functionstatic int []phi = new int[N];// To store prefix sum tablestatic int []pref = new int[N];// Compute Totients of all numbers// smaller than or equal to Nstatic void precompute(){ // Make phi[1] = 0 since 1 // cannot form any pair phi[1] = 0; // Initialise all remaining // phi[] with i for(int i = 2; i < N; i++) phi[i] = i; // Compute remaining phi for(int p = 2; p < N; p++) { // If phi[p] is not computed already, // then number p is prime if (phi[p] == p) { // phi of prime number is p-1 phi[p] = p - 1; // Update phi of all multiples of p for(int i = 2 * p; i < N; i += p) { // Add the contribution of p // to its multiple i by multiplying // it with (1 - 1/p) phi[i] = (phi[i] / p) * (p - 1); } } }}// Function to store prefix sum tablestatic void prefix(){ // Prefix Sum of all // Euler's Totient Values for(int i = 1; i < N; i++) pref[i] = pref[i - 1] + phi[i];}static void find_pairs(int n){ // Total number of pairs // that can be formed int total = (n * (n - 1)) / 2; int ans = total - pref[n]; Console.Write("Number of pairs from 1 to " + n + " are " + ans + "\n");}// Driver Codepublic static void Main(String[] args){ // Function call to compute all phi precompute(); // Function call to store // all prefix sum prefix(); int []q = {5, 7}; int n = q.Length; for(int i = 0; i < n; i++) { find_pairs(q[i]); }}}// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript program to find the count of pairs// from 1 to N such that their LCM// is not equal to their product var N = 100005; // To store Euler's Totient Function var phi = Array(N).fill(0); // To store prefix sum table var pref = Array(N).fill(0); // Compute Totients of all numbers // smaller than or equal to N function precompute() { // Make phi[1] = 0 since 1 cannot form any pair phi[1] = 0; // Initialise all remaining phi with i for (i = 2; i < N; i++) phi[i] = i; // Compute remaining phi for (p = 2; p < N; p++) { // If phi[p] is not computed already, // then number p is prime if (phi[p] == p) { // phi of prime number is p-1 phi[p] = p - 1; // Update phi of all multiples of p for (i = 2 * p; i < N; i += p) { // Add the contribution of p // to its multiple i by multiplying // it with (1 - 1/p) phi[i] = (phi[i] / p) * (p - 1); } } } } // Function to store prefix sum table function prefix() { // Prefix Sum of all Euler's Totient Values for (i = 1; i < N; i++) pref[i] = pref[i - 1] + phi[i]; } function find_pairs(n) { // Total number of pairs that can be formed var total = (n * (n - 1)) / 2; var ans = total - pref[n]; document.write("Number of pairs from 1 to " + n + " are " + ans + "<br/>"); } // Driver Code // Function call to compute all phi precompute(); // Function call to store all prefix sum prefix(); var q = [ 5, 7 ]; var n = q.length; for (i = 0; i < n; i++) { find_pairs(q[i]); }// This code contributed by Rajput-Ji </script> |
Output:
Number of pairs from 1 to 5 are 1 Number of pairs from 1 to 7 are 4
Time Complexity: O(n2)
Auxiliary Space: O(n)
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!
