Dada una array arr[] de N elementos. La tarea es encontrar el conteo de enteros positivos que dividen todos los elementos del arreglo.
Ejemplos:
Entrada: arr[] = {2, 8, 10, 6}
Salida: 2
1 y 2 son los únicos números enteros que dividen
todos los elementos de la array dada.
Entrada: arr[] = {6, 12, 18, 12, 6}
Salida: 4
Enfoque: Sabemos que el entero máximo que dividirá todos los elementos del arreglo será el mcd del arreglo y todos los demás enteros que dividirán todos los elementos del arreglo tendrán que ser los factores de este mcd. Por lo tanto, el conteo de enteros válidos será igual al conteo de factores del gcd de todos los elementos del arreglo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count of // the required integers int getCount(int a[], int n) { // To store the gcd of the array elements int gcd = 0; for (int i = 0; i < n; i++) gcd = __gcd(gcd, a[i]); // To store the count of factors // of the found gcd int cnt = 0; for (int i = 1; i * i <= gcd; i++) { if (gcd % i == 0) { // If g is a perfect square if (i * i == gcd) cnt++; // Factors appear in pairs else cnt += 2; } } return cnt; } // Driver code int main() { int a[] = { 4, 16, 1024, 48 }; int n = sizeof(a) / sizeof(a[0]); cout << getCount(a, n); return 0; }
Java
// Java implementation of the approach class GFG { // Recursive function to return gcd static int calgcd(int a, int b) { if (b == 0) return a; return calgcd(b, a % b); } // Function to return the count of // the required integers static int getCount(int [] a, int n) { // To store the gcd of the array elements int gcd = 0; for (int i = 0; i < n; i++) gcd = calgcd(gcd, a[i]); // To store the count of factors // of the found gcd int cnt = 0; for (int i = 1; i * i <= gcd; i++) { if (gcd % i == 0) { // If g is a perfect square if (i * i == gcd) cnt++; // Factors appear in pairs else cnt += 2; } } return cnt; } // Driver code public static void main (String[] args) { int [] a = { 4, 16, 1024, 48 }; int n = a.length; System.out.println(getCount(a, n)); } } // This code is contributed by ihritik
Python3
# Python3 implementation of the approach # Function to return the count of # the required integers from math import gcd as __gcd def getCount(a, n): # To store the gcd of the array elements gcd = 0 for i in range(n): gcd = __gcd(gcd, a[i]) # To store the count of factors # of the found gcd cnt = 0 for i in range(1, gcd + 1): if i * i > gcd: break if (gcd % i == 0): # If g is a perfect square if (i * i == gcd): cnt += 1 # Factors appear in pairs else: cnt += 2 return cnt # Driver code a = [4, 16, 1024, 48] n = len(a) print(getCount(a, n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach using System; class GFG { // Recursive function to return gcd static int calgcd(int a, int b) { if (b == 0) return a; return calgcd(b, a % b); } // Function to return the count of // the required integers static int getCount(int [] a, int n) { // To store the gcd of the array elements int gcd = 0; for (int i = 0; i < n; i++) gcd = calgcd(gcd, a[i]); // To store the count of factors // of the found gcd int cnt = 0; for (int i = 1; i * i <= gcd; i++) { if (gcd % i == 0) { // If g is a perfect square if (i * i == gcd) cnt++; // Factors appear in pairs else cnt += 2; } } return cnt; } // Driver code public static void Main () { int [] a = { 4, 16, 1024, 48 }; int n = a.Length; Console.WriteLine(getCount(a, n)); } } // This code is contributed by ihritik
Javascript
<script> // Javascript implementation of the approach function calgcd(a, b) { if (b == 0) return a; return calgcd(b, a % b); } // Function to return the count of // the required integers function getCount(a, n) { // To store the gcd of the array elements let gcd = 0; for (let i = 0; i < n; i++) gcd = calgcd(gcd, a[i]); // To store the count of factors // of the found gcd let cnt = 0; for (let i = 1; i * i <= gcd; i++) { if (gcd % i == 0) { // If g is a perfect square if (i * i == gcd) cnt++; // Factors appear in pairs else cnt += 2; } } return cnt; } // Driver code let a = [ 4, 16, 1024, 48 ]; let n = a.length; document.write(getCount(a, n)); </script>
Producción:
3