Dada una array de pares arr[] de dos números {N, M} , la tarea es encontrar el recuento máximo de divisores comunes para cada par N y M de modo que cada par entre el divisor común sea coprimo.
Un número x es un divisor común de N y M si, N%x = 0 y M%x = 0 .
Dos números son coprimos si su máximo común divisor es 1.
Ejemplos:
Entrada: arr[][] = {{12, 18}, {420, 660}}
Salida: 3 4
Explicación:
Para el par (12, 18):
{1, 2, 3} son divisores comunes de 12 y 18 , y son coprimos por parejas.
Para el par (420, 660):
{1, 2, 3, 5} son divisores comunes de 12 y 18, y son coprimos por pares.
Entrada: arr[][] = {{8, 18}, {20, 66}}
Salida: 2 2
Enfoque: El recuento máximo de divisores comunes de N y M tal que el MCD de todos los pares entre ellos siempre es 1 es 1 y todos los divisores primos comunes de N y M . Para contar todos los divisores primos comunes, la idea es encontrar el MCD (digamos G ) de los dos números dados y luego contar el número de divisores primos del número G.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the gcd of
// two numbers
int gcd(int x, int y)
{
if (x % y == 0)
return y;
else
return gcd(y, x % y);
}
// Function to of pairwise co-prime
// and common divisors of two numbers
int countPairwiseCoprime(int N, int M)
{
// Initialize answer with 1,
// to include 1 in the count
int answer = 1;
// Count of primes of gcd(N, M)
int g = gcd(N, M);
int temp = g;
// Finding prime factors of gcd
for (int i = 2; i * i <= g; i++) {
// Increment count if it is
// divisible by i
if (temp % i == 0) {
answer++;
while (temp % i == 0)
temp /= i;
}
}
if (temp != 1)
answer++;
// Return the total count
return answer;
}
void countCoprimePair(int arr[][2], int N)
{
// Function Call for each pair
// to calculate the count of
// pairwise co-prime divisors
for (int i = 0; i < N; i++) {
cout << countPairwiseCoprime(arr[i][0],
arr[i][1])
<< ' ';
}
}
// Driver Code
int main()
{
// Given array of pairs
int arr[][2] = { { 12, 18 }, { 420, 660 } };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
countCoprimePair(arr, N);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find the gcd of
// two numbers
static int gcd(int x, int y)
{
if (x % y == 0)
return y;
else
return gcd(y, x % y);
}
// Function to of pairwise co-prime
// and common divisors of two numbers
static int countPairwiseCoprime(int N, int M)
{
// Initialize answer with 1,
// to include 1 in the count
int answer = 1;
// Count of primes of gcd(N, M)
int g = gcd(N, M);
int temp = g;
// Finding prime factors of gcd
for (int i = 2; i * i <= g; i++)
{
// Increment count if it is
// divisible by i
if (temp % i == 0)
{
answer++;
while (temp % i == 0)
temp /= i;
}
}
if (temp != 1)
answer++;
// Return the total count
return answer;
}
static void countCoprimePair(int arr[][], int N)
{
// Function Call for each pair
// to calculate the count of
// pairwise co-prime divisors
for (int i = 0; i < N; i++)
{
System.out.print(countPairwiseCoprime(arr[i][0],
arr[i][1]) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array of pairs
int arr[][] = { { 12, 18 }, { 420, 660 } };
int N = arr.length;
// Function Call
countCoprimePair(arr, N);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach # Function to find the gcd of # two numbers def gcd(x, y): if (x % y == 0): return y else: return gcd(y, x % y) # Function to of pairwise co-prime # and common divisors of two numbers def countPairwiseCoprime(N, M): # Initialize answer with 1, # to include 1 in the count answer = 1 # Count of primes of gcd(N, M) g = gcd(N, M) temp = g # Finding prime factors of gcd for i in range(2, g + 1): if i * i > g: break # Increment count if it is # divisible by i if (temp % i == 0) : answer += 1 while (temp % i == 0): temp //= i if (temp != 1): answer += 1 # Return the total count return answer def countCoprimePair(arr, N): # Function Call for each pair # to calculate the count of # pairwise co-prime divisors for i in range(N): print(countPairwiseCoprime(arr[i][0], arr[i][1]), end = " ") # Driver Code if __name__ == '__main__': # Given array of pairs arr= [ [ 12, 18 ], [ 420, 660 ] ] N = len(arr) # Function Call countCoprimePair(arr, N) # This code is contributed by Mohit Kumar
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the gcd of
// two numbers
static int gcd(int x, int y)
{
if (x % y == 0)
return y;
else
return gcd(y, x % y);
}
// Function to of pairwise co-prime
// and common divisors of two numbers
static int countPairwiseCoprime(int N, int M)
{
// Initialize answer with 1,
// to include 1 in the count
int answer = 1;
// Count of primes of gcd(N, M)
int g = gcd(N, M);
int temp = g;
// Finding prime factors of gcd
for (int i = 2; i * i <= g; i++)
{
// Increment count if it is
// divisible by i
if (temp % i == 0)
{
answer++;
while (temp % i == 0)
temp /= i;
}
}
if (temp != 1)
answer++;
// Return the total count
return answer;
}
static void countCoprimePair(int [,]arr, int N)
{
// Function Call for each pair
// to calculate the count of
// pairwise co-prime divisors
for (int i = 0; i < N; i++)
{
Console.Write(countPairwiseCoprime(arr[i, 0],
arr[i, 1]) + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array of pairs
int [,]arr = { { 12, 18 }, { 420, 660 } };
int N = arr.GetLength(0);
// Function Call
countCoprimePair(arr, N);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program for the above approach
// Function to find the gcd of
// two numbers
function gcd(x, y)
{
if (x % y == 0)
return y;
else
return gcd(y, x % y);
}
// Function to of pairwise co-prime
// and common divisors of two numbers
function countPairwiseCoprime(N, M)
{
// Initialize answer with 1,
// to include 1 in the count
let answer = 1;
// Count of primes of gcd(N, M)
let g = gcd(N, M);
let temp = g;
// Finding prime factors of gcd
for (let i = 2; i * i <= g; i++)
{
// Increment count if it is
// divisible by i
if (temp % i == 0)
{
answer++;
while (temp % i == 0)
temp /= i;
}
}
if (temp != 1)
answer++;
// Return the total count
return answer;
}
function countCoprimePair(arr, N)
{
// Function Call for each pair
// to calculate the count of
// pairwise co-prime divisors
for (let i = 0; i < N; i++)
{
document.write(countPairwiseCoprime(arr[i][0],
arr[i][1]) + " ");
}
}
// Driver Code
// Given array of pairs
let arr = [[ 12, 18 ], [ 420, 660 ]];
let N = arr.length;
// Function Call
countCoprimePair(arr, N);
</script>
Producción:
3 4
Complejidad de tiempo: O(X*(sqrt(N) + sqrt(M))), donde X es el número de pares y N & M son dos pares en arr[].
Espacio Auxiliar: O(1)