Contar pares en Array cuyo producto es divisible por K

Dada una array vec y un entero K , cuente el número de pares (i, j) tales que vec [i]* vec [j] es divisible por K donde i<j.

Ejemplos:

Entrada : vec = {1, 2, 3, 4, 5, 6}, K = 4
Salida : 6
Explicación : Los pares de índices (0, 3), (1, 3), (2, 3), (3 , 4), (3, 5) y (1, 5) cumplen la condición ya que sus productos son respectivamente 4, 8, 12, 20, 24, 12 
que son divisibles por k=4.
Como hay 6 pares, la cuenta será 6.

Entrada : vec = {1, 2, 3, 4}, K = 2
Salida : 5
Explicación : Los pares de índices (0, 1), (1, 2), (1, 3), (0, 3), (2, 3) cumplen la condición ya que sus productos son respectivamente 2, 6, 8, 4, 12 que son divisibles por k=2.
Como hay 5 pares, la cuenta será 5.

Enfoque ingenuo: el enfoque más simple para resolver este problema es encontrar todos los pares y, para cada par, verificar si su producto es divisible por K.

Complejidad temporal: O(N^2)
Espacio auxiliar: O(1)

Enfoque eficiente: el problema anterior se puede resolver de manera eficiente con la ayuda de GCD.

Sabemos que el producto de A y B es divisible por un número B si MCD(A, B) = B.

De manera similar (vec[i] * vec[j]) será divisible por K si su MCD es K. 

Siga los pasos a continuación para resolver el problema: 

• Cree un contador de tamaño 10 ^ 5 + 1 para precalcular el recuento de cuántos números son divisibles por un número num (digamos) (para todos los números 1 a 10 ^ 5).
• Luego, solo necesitamos hacer un bucle para cada elemento o vector y encontrar el número restante (factor_restante) que se debe multiplicar para que el GCD sea igual a k.
• Luego, para este número, el recuento de pares será tanto como el múltiplo del factor restante presente en la array (ignorando el número en sí).
• Por lo tanto, sumando el recuento de pares para cada i en vec obtendremos nuestra respuesta, dividiremos la respuesta final por 2 ya que hemos contado cada par dos veces para cualquier par (i, j) y eliminaremos los duplicados.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for Count number of pairs
// in a vector such that
// product is divisible by K
 
#include <bits/stdc++.h>
using namespace std;
 
// Precalculate count array to see numbers
// that are divisible by a number num (say)
// for all num 1 to 10^5
int countarr[100001];
int count_of_multiples[100001];
 
long long countPairs(vector<int>& vec, int k)
{
    int n = vec.size();
    for (int i = 0; i < n; i++)
 
        // counting frequency of  each
        // element in vector
        countarr[vec[i]]++;
 
    for (int i = 1; i < 100001; i++) {
        for (int j = i; j < 100001; j = j + i)
 
            // counting total elements present in
            // array which are multiple of i
            count_of_multiples[i] += countarr[j];
    }
 
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long factor = __gcd(k, vec[i]);
        long long remaining_factor = (k / factor);
        long long j = count_of_multiples[remaining_factor];
 
        // if vec[i] itself is multiple of
        // remaining factor then we to ignore
        // it as  i!=j
        if (vec[i] % remaining_factor == 0)
            j--;
        ans += j;
    }
 
    // as we have counted any distinct pair
    // (i, j) two times, we need to take them
    // only once
    ans /= 2;
 
    return ans;
}
 
// Driver code
int main()
{
    vector<int> vec = { 1, 2, 3, 4, 5, 6 };
    int k = 4;
    cout << countPairs(vec, k) << endl;
}

// Java program for Count number of pairs
// in a vector such that
// product is divisible by K
import java.util.*;
public class GFG {
 
  // Precalculate count array to see numbers
  // that are divisible by a number num (say)
  // for all num 1 to 10^5
  static int[] countarr = new int[100001];
  static int[] count_of_multiples = new int[100001];
 
  // Recursive function to return
  // gcd of a and b
  static int gcd(int a, int b)
  {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }
 
  static long countPairs(int[] vec, int k)
  {
    int n = vec.length;
    for (int i = 0; i < n; i++)
 
      // counting frequency of  each
      // element in vector
      countarr[vec[i]]++;
 
    for (int i = 1; i < 100001; i++) {
      for (int j = i; j < 100001; j = j + i)
 
        // counting total elements present in
        // array which are multiple of i
        count_of_multiples[i] += countarr[j];
    }
 
    long ans = 0;
    for (int i = 0; i < n; i++) {
      long factor = gcd(k, vec[i]);
      long remaining_factor = (k / factor);
      long j = count_of_multiples[(int)remaining_factor];
 
      // if vec[i] itself is multiple of
      // remaining factor then we to ignore
      // it as  i!=j
      if (vec[i] % remaining_factor == 0)
        j--;
      ans += j;
    }
 
    // as we have counted any distinct pair
    // (i, j) two times, we need to take them
    // only once
    ans /= 2;
 
    return ans;
  }
 
  // Driver code
  public static void main(String args[])
  {
    int[] vec = { 1, 2, 3, 4, 5, 6 };
    int k = 4;
    System.out.println(countPairs(vec, k));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# Python program for Count number of pairs
# in a vector such that
# product is divisible by K
import math
 
# Precalculate count array to see numbers
# that are divisible by a number num (say)
# for all num 1 to 10^5
countarr = [0] * 100001
count_of_multiples = [0] * 100001
 
def countPairs(vec, k):
 
    n = len(vec)
    for i in range(0, n):
 
        # counting frequency of  each
        # element in vector
        countarr[vec[i]] += 1
 
    for i in range(1, 100001):
        j = i
        while(j < 100001):
 
            # counting total elements present in
            # array which are multiple of i
            count_of_multiples[i] += countarr[j]
            j += i
 
    ans = 0
    for i in range(0, n):
        factor = math.gcd(k, vec[i])
        remaining_factor = (k // factor)
        j = count_of_multiples[remaining_factor]
 
        # if vec[i] itself is multiple of
        # remaining factor then we to ignore
        # it as  i!=j
        if (vec[i] % remaining_factor == 0):
            j -= 1
        ans += j
 
    # as we have counted any distinct pair
    # (i, j) two times, we need to take them
    # only once
    ans //= 2
    return ans
 
# Driver code
vec = [1, 2, 3, 4, 5, 6]
k = 4
print(countPairs(vec, k))
 
# This code is contributed by Samim Hossain Mondal.

// C# program for Count number of pairs
// in a vector such that
// product is divisible by K
 
using System;
class GFG {
 
  // Precalculate count array to see numbers
  // that are divisible by a number num (say)
  // for all num 1 to 10^5
  static int[] countarr = new int[100001];
  static int[] count_of_multiples = new int[100001];
 
  // Recursive function to return
  // gcd of a and b
  static int gcd(int a, int b)
  {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }
 
  static long countPairs(int[] vec, int k)
  {
    int n = vec.Length;
    for (int i = 0; i < n; i++)
 
      // counting frequency of  each
      // element in vector
      countarr[vec[i]]++;
 
    for (int i = 1; i < 100001; i++) {
      for (int j = i; j < 100001; j = j + i)
 
        // counting total elements present in
        // array which are multiple of i
        count_of_multiples[i] += countarr[j];
    }
 
    long ans = 0;
    for (int i = 0; i < n; i++) {
      long factor = gcd(k, vec[i]);
      long remaining_factor = (k / factor);
      long j = count_of_multiples[remaining_factor];
 
      // if vec[i] itself is multiple of
      // remaining factor then we to ignore
      // it as  i!=j
      if (vec[i] % remaining_factor == 0)
        j--;
      ans += j;
    }
 
    // as we have counted any distinct pair
    // (i, j) two times, we need to take them
    // only once
    ans /= 2;
 
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int[] vec = { 1, 2, 3, 4, 5, 6 };
    int k = 4;
    Console.WriteLine(countPairs(vec, k));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript program for Count number of pairs
    // in a vector such that
    // product is divisible by K
 
    // Precalculate count array to see numbers
    // that are divisible by a number num (say)
    // for all num 1 to 10^5
    let countarr = new Array(100001).fill(0);
    let count_of_multiples = new Array(100001).fill(0);
 
    // Function for __gcd
    const __gcd = (a, b) => {
        if (a % b == 0) return b;
 
        return __gcd(b, a % b);
    }
 
    const countPairs = (vec, k) => {
        let n = vec.length;
        for (let i = 0; i < n; i++)
 
            // counting frequency of each
            // element in vector
            countarr[vec[i]]++;
 
        for (let i = 1; i < 100001; i++) {
            for (let j = i; j < 100001; j = j + i)
 
                // counting total elements present in
                // array which are multiple of i
                count_of_multiples[i] += countarr[j];
        }
 
        let ans = 0;
        for (let i = 0; i < n; i++) {
            let factor = __gcd(k, vec[i]);
            let remaining_factor = (k / factor);
            let j = count_of_multiples[remaining_factor];
 
            // if vec[i] itself is multiple of
            // remaining factor then we to ignore
            // it as i!=j
            if (vec[i] % remaining_factor == 0)
                j--;
            ans += j;
        }
 
        // as we have counted any distinct pair
        // (i, j) two times, we need to take them
        // only once
        ans /= 2;
        return ans;
    }
 
    // Driver code
    let vec = [1, 2, 3, 4, 5, 6];
    let k = 4;
    document.write(countPairs(vec, k));
 
// This code is contributed by rakeshsahni
 
</script>

6

Complejidad de tiempo: O(N*log(N)) 
Espacio auxiliar: O(N)