Find the number of pairs with given GCD and LCM represented by prime factorization - Coding

Given two large number X and Y in the form of arrays as their prime factorization of size N and M. X = A[1]^B[1] * A[2]^B[2] * A[3]^B[3] * ……. * A[N]^B[N] and Y = C[1]^D[1] * C[2]^D[2] * C[3] ^D[3]* ….. * C[M]^D[M], the task for this problem is to find out the number of pairs (a, b) such that LCM(a, b) is X and GCD(a, b) is Y. Since the number of pair can be large print them modulo 10⁹ + 7.

Examples:

Input: A[] = { 2, 3, 5, 7 }, B[] = { 2, 1, 1, 2 }, N = 4, C[] = { 3, 7 }, D[] = { 1, 1 }, M = 2
Output: 8
Explanation: X = 2²*3¹*5¹*7²= 2940, Y = 3¹*7¹= 21

p = 21, q = 2940

p = 84, q = 735

p = 105, q = 588

p = 147, q = 420

p = 420, q = 147

p = 588, q = 105

p = 735, q = 84

p = 2940, q = 21

Input: A[] = { 2, 5 }, B[] = { 1, 1 }, N = 2, C[] = { 2, 3 }, D[] = { 1, 1 }, M = 2
Output: 0
Explanation: There are no pairs that satisfy the above condition

Efficient Approach: To solve the problem follow the below idea:

We have prime factorization of X and Y given in the form of arrays. By the property we know To find the greatest common divisor (GCD) of two or more numbers, you identify the common prime factors and take the smallest exponent for each prime factor. To find the least common multiple (LCM), you consider all the prime factors and take the highest exponent for each prime factor.

Observation 1: C[i]^D[i] is prime factorization of Y which is suppose to be our GCD that means this is the minimum prime factor either our desired numbers a or b can have.

Observation 2: A[i]^B[i] is prime factorization of X which is suppose to be our LCM that means this is the maximum prime factor either our desired numbers a or b can have.

For eg:

X = 2940 = 2²*3¹*5¹*7²

Y = 21 = 2⁰*3¹*5⁰*7¹

p and q will share above prime factors to form all possible combinations.

we have two ways to insert 2^2 and 2^0 in either of p and q.

we have only one way to insert 3^1 and 3^1 in either of p and q (since they are identical).

we have two ways to insert 5^1 and 5^0 in either of p and q.

we have two ways to insert 7^2 and 7^1 in either of p and q.

by multiplication principle, total combination will be = 2 * 1 * 2 * 2 = 8

Below are the steps for the above approach:

Declaring hashmap named HashMap1[] and HashMap2[].
Filling HashMap1[A[i]] = B[i] for all i from 1 to N .
Filling HashMap2[C[i]] = D[i] for all i from 1 to M .
Iterating on all M elements of array C[] and check if HashMap2[C[i]] is greater than HashMap1[C[i]] if it is then return 0.
initialize the variable ans with value 1.
Iterating over all N elements of array A[] if HashMap1[A[i]] is greater than HashMap2[A[i]] if it is then multiply ans with 2.
return ans.

Below is the implementation of the above approach:

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
 
// Function to find the number of pairs
// with given LCM and GCD
int numberOfPairs(int A[], int B[], int N, int C[], int D[],
                  int M)
{
 
    // Declaring Hashmap for mapping
    // each values
    unordered_map<int, int> HashMap1, HashMap2;
 
    // Filling the Hashmap1
    for (int i = 0; i < N; i++) {
        HashMap1[A[i]] = B[i];
    }
 
    // Filling the Hashmap2
    for (int i = 0; i < M; i++) {
        HashMap2[C[i]] = D[i];
    }
 
    // If any prime factor has greater power
    // in GCD than LCM then no pairs possible
    for (int i = 0; i < M; i++) {
        if (HashMap2[C[i]] > HashMap1[C[i]])
            return 0;
    }
 
    // Initializing answer variable
    int ans = 1;
 
    // Iterating over all N elements
    for (int i = 0; i < N; i++) {
        if (HashMap1[A[i]] > HashMap2[A[i]])
            ans = (ans * 2) % mod;
    }
 
    // Return answer
    return ans;
}
 
// Driver Code
int32_t main()
{
 
    // Input 1
    int A[] = { 2, 3, 5, 7 }, B[] = { 2, 1, 1, 2 }, N = 4;
    int C[] = { 3, 7 }, D[] = { 1, 1 }, M = 2;
 
    // Function Call
    cout << numberOfPairs(A, B, N, C, D, M) << endl;
 
    // Input 2
    int A1[] = { 2, 5 }, B1[] = { 1, 1 }, N1 = 2;
    int C1[] = { 2, 3 }, D1[] = { 1, 1 }, M1 = 2;
 
    // Function Call
    cout << numberOfPairs(A1, B1, N1, C1, D1, M1) << endl;
 
    return 0;
}

Java

import java.util.HashMap;
 
class Main {
 
    static final int mod = 1000000007;
 
    // Function to find the number of pairs
    // with given LCM and GCD
    static int numberOfPairs(int A[], int B[], int N, int C[], int D[], int M) {
 
        // Declaring Hashmap for mapping each value
        HashMap<Integer, Integer> HashMap1 = new HashMap<>();
        HashMap<Integer, Integer> HashMap2 = new HashMap<>();
 
        // Filling the Hashmap1
        for (int i = 0; i < N; i++) {
            HashMap1.put(A[i], B[i]);
        }
 
        // Filling the Hashmap2
        for (int i = 0; i < M; i++) {
            HashMap2.put(C[i], D[i]);
        }
 
        // If any prime factor has greater power
        // in GCD than LCM then no pairs possible
        for (int i = 0; i < M; i++) {
            if (!HashMap1.containsKey(C[i]) || HashMap2.get(C[i]) > HashMap1.get(C[i]))
                return 0;
        }
 
        // Initializing answer variable
        int ans = 1;
 
        // Iterating over all N elements
        for (int i = 0; i < N; i++) {
            if (!HashMap2.containsKey(A[i]) || HashMap1.get(A[i]) > HashMap2.get(A[i]))
                ans = (int) (ans * 2) % mod;
        }
 
        // Return answer
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args) {
 
        // Input 1
        int A[] = {2, 3, 5, 7}, B[] = {2, 1, 1, 2}, N = 4;
        int C[] = {3, 7}, D[] = {1, 1}, M = 2;
 
        // Function Call
        System.out.println(numberOfPairs(A, B, N, C, D, M));
 
        // Input 2
        int A1[] = {2, 5}, B1[] = {1, 1}, N1 = 2;
        int C1[] = {2, 3}, D1[] = {1, 1}, M1 = 2;
 
        // Function Call
        System.out.println(numberOfPairs(A1, B1, N1, C1, D1, M1));
    }
}

Python3

def numberOfPairs(A, B, N, C, D, M):
    mod = 10**9 + 7
 
    # Create dictionaries to store values
    HashMap1 = {}
    HashMap2 = {}
 
    # Filling HashMap1
    for i in range(N):
        HashMap1[A[i]] = B[i]
 
    # Filling HashMap2
    for i in range(M):
        HashMap2[C[i]] = D[i]
 
    # If any prime factor has greater power in GCD than LCM, then no pairs are possible
    for i in range(M):
        if C[i] in HashMap2 and HashMap2[C[i]] > HashMap1.get(C[i], 0):
            return 0
 
    # Initializing the answer variable
    ans = 1
 
    # Iterating over all N elements
    for i in range(N):
        if A[i] in HashMap1 and HashMap1[A[i]] > HashMap2.get(A[i], 0):
            ans = (ans * 2) % mod
 
    # Return answer
    return ans
 
# Input 1
A = [2, 3, 5, 7]
B = [2, 1, 1, 2]
N = 4
C = [3, 7]
D = [1, 1]
M = 2
 
# Function Call
print(numberOfPairs(A, B, N, C, D, M))
 
# Input 2
A1 = [2, 5]
B1 = [1, 1]
N1 = 2
C1 = [2, 3]
D1 = [1, 1]
M1 = 2
 
# Function Call
print(numberOfPairs(A1, B1, N1, C1, D1, M1))

C#

using System;
using System.Collections.Generic;
 
class GFG {
    static readonly int mod = 1000000007;
 
    // Function to find the number of pairs
    // with given LCM and GCD
    static int NumberOfPairs(int[] A, int[] B, int N,
                             int[] C, int[] D, int M)
    {
        // Declaring Dictionary for mapping each value
        Dictionary<int, int> HashMap1
            = new Dictionary<int, int>();
        Dictionary<int, int> HashMap2
            = new Dictionary<int, int>();
 
        // Filling the HashMap1
        for (int i = 0; i < N; i++) {
            HashMap1[A[i]] = B[i];
        }
 
        // Filling the HashMap2
        for (int i = 0; i < M; i++) {
            HashMap2[C[i]] = D[i];
        }
 
        // If any prime factor has greater power
        // in GCD than LCM then no pairs possible
        for (int i = 0; i < M; i++) {
            if (!HashMap1.ContainsKey(C[i])
                || HashMap2[C[i]] > HashMap1[C[i]])
                return 0;
        }
 
        // Initializing answer variable
        int ans = 1;
 
        // Iterating over all N elements
        for (int i = 0; i < N; i++) {
            if (!HashMap2.ContainsKey(A[i])
                || HashMap1[A[i]] > HashMap2[A[i]])
                ans = (int)(ans * 2L % mod);
        }
 
        // Return answer
        return ans;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        // Input 1
        int[] A = { 2, 3, 5, 7 }, B = { 2, 1, 1, 2 },
              C = { 3, 7 }, D = { 1, 1 };
        int N = 4, M = 2;
 
        // Function Call
        Console.WriteLine(NumberOfPairs(A, B, N, C, D, M));
 
        // Input 2
        int[] A1 = { 2, 5 }, B1 = { 1, 1 }, C1 = { 2, 3 },
              D1 = { 1, 1 };
        int N1 = 2, M1 = 2;
 
        // Function Call
        Console.WriteLine(
            NumberOfPairs(A1, B1, N1, C1, D1, M1));
    }
}

Javascript

function GFG(A, B, N, C, D, M) {
    const mod = 1000000007; // 10^9 + 7
    // Create dictionaries to store values
    const HashMap1 = new Map();
    const HashMap2 = new Map();
    // Filling HashMap1
    for (let i = 0; i < N; i++) {
        HashMap1.set(A[i], B[i]);
    }
    // Filling HashMap2
    for (let i = 0; i < M; i++) {
        HashMap2.set(C[i], D[i]);
    }
 
    // If any prime factor has greater power in GCD than LCM
    // then no pairs are possible
    for (let i = 0; i < M; i++) {
        if (HashMap2.has(C[i]) && HashMap2.get(C[i]) > (HashMap1.get(C[i]) || 0)) {
            return 0;
        }
    }
    // Initializing the answer variable
    let ans = 1;
    // Iterating over all N elements
    for (let i = 0; i < N; i++) {
        if (HashMap1.has(A[i]) && HashMap1.get(A[i]) > (HashMap2.get(A[i]) || 0)) {
            ans = (ans * 2) % mod;
        }
    }
    // Return the answer
    return ans;
}
// Input 1
const A = [2, 3, 5, 7];
const B = [2, 1, 1, 2];
const N = 4;
const C = [3, 7];
const D = [1, 1];
const M = 2;
// Function Call
console.log(GFG(A, B, N, C, D, M));
// Input 2
const A1 = [2, 5];
const B1 = [1, 1];
const N1 = 2;
const C1 = [2, 3];
const D1 = [1, 1];
const M1 = 2;
// Function Call
console.log(GFG(A1, B1, N1, C1, D1, M1));

Output

8
0

Time Complexity: O(N)
Auxiliary Space: O(N)

Reffered: https://www.geeksforgeeks.org

Arrays

Related
Longest Prefix Subsequence matching Fibonacci Sequence
Minimum Operations to Reduce X to Zero
Minimum sum of Quotients after performing the given operation
Find Next Optimal Range in Array
Minimum Jumps with Specific NUM Value

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	10