Dado un entero N , la tarea es generar una array de N enteros distintos . Tal que el MCD de todos los elementos del arreglo es 1, pero ningún par de elementos es coprimo, es decir, para cualquier par (A[i], A[j]) del arreglo MCD(A[i], A[ j]) ≠ 1.
Nota: Si es posible más de 1 respuesta, imprima cualquiera de ellas.
Ejemplos:
Entrada: N = 4
Salida: 30 70 42 105
Explicación: MCD(30, 70, 42, 105) = 1.
MCD(30, 70) = 10, MCD(30, 42) = 6, MCD(30, 105) = 15, MCD(70, 42) = 14, MCD(70, 105) = 35, MCD(42, 105) = 21.
Por lo tanto, se puede ver que el MCD de todos los elementos es 1, mientras que el MCD de todos los pares posibles es mayor que 1.Entrada: N = 6
Salida: 10 15 6 12 24 48
Planteamiento: El problema se puede resolver con base en la siguiente observación:
Supongamos A 1 , A 2 , A 3 . . . A N son N números primos. Sea su producto P, es decir, P = A 1 * A 2 * A 3 . . .*A N.
Entonces, la secuencia P/A 1 , P/A 2 . . . P/A N = (A 2 * A 3 . . . A N ), (A 1 * A 3 . . . A N ), . . ., (A 1 * A 2 . . . A N-1 )
Esta secuencia tiene al menos un factor común entre cualquier par de elementos, pero el GCD general es 1
Esto se puede hacer siguiendo los pasos que se detallan a continuación:
- Si N = 2, devuelva -1, ya que tal secuencia no es posible para N = 2.
- Almacene los primeros N números primos usando la Tamiz de Eratóstenes (digamos en un vector v ).
- Calcule el producto de todos los elementos del vector «v» y guárdelo en una variable (digamos «producto»).
- Ahora, itere de i = 0 a N-1 y en cada iteración almacene el i-ésimo elemento de respuesta como (producto/v[i]) .
- Devuelve el vector resultante.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int M = 100001;
bool primes[M + 1];
// Function to form an array such that
// pairwise gcd of all elements is not 1
// and gcd of whole sequence is 1
void printArray(int N)
{
// Such sequence is not possible for N=2
if (N == 2) {
cout << -1 << endl;
return;
}
// storing primes upto M using sieve
for (int i = 0; i < M; i++)
primes[i] = 1;
primes[0] = 0;
primes[1] = 0;
for (int i = 2; i * i <= M; i++) {
if (primes[i] == 1) {
for (int j = i * i; j <= M;
j += i) {
primes[j] = 0;
}
}
}
// Storing first N primes in vector v
vector<int> v;
for (int i = 0; i < M; i++) {
if (v.size() < N
&& primes[i] == 1) {
v.push_back(i);
}
}
// Calculating product of
// first N prime numbers
int product = 1;
vector<int> answer;
for (auto it : v) {
product *= it;
}
// Calculating answer sequence
for (int i = 0; i < N; i++) {
int num = product / v[i];
answer.push_back(num);
}
// Printing the answer
for (int i = 0; i < N; i++) {
cout << answer[i] << " ";
}
}
// Driver Code
int32_t main()
{
int N = 4;
// Function call
printArray(N);
return 0;
}
Java
// Java code to implement the approach
import java.util.ArrayList;
class GFG {
static int M = 100001;
static int[] primes = new int[M + 1];
// Function to form an array such that
// pairwise gcd of all elements is not 1
// and gcd of whole sequence is 1
static void printArray(int N)
{
// Such sequence is not possible for N=2
if (N == 2) {
System.out.println(-1);
return;
}
// storing primes upto M using sieve
for (int i = 0; i < M; i++)
primes[i] = 1;
primes[0] = 0;
primes[1] = 0;
for (int i = 2; i * i <= M; i++) {
if (primes[i] == 1) {
for (int j = i * i; j <= M; j += i) {
primes[j] = 0;
}
}
}
// Storing first N primes in arraylist v
ArrayList<Integer> v = new ArrayList<Integer>();
for (int i = 0; i < M; i++) {
if (v.size() < N && primes[i] == 1) {
v.add(i);
}
}
// Calculating product of
// first N prime numbers
int product = 1;
ArrayList<Integer> answer
= new ArrayList<Integer>();
;
for (int i = 0; i < v.size(); i++) {
product *= v.get(i);
}
// Calculating answer sequence
for (int i = 0; i < N; i++) {
int num = product / v.get(i);
answer.add(num);
}
// Printing the answer
for (int i = 0; i < N; i++) {
System.out.print(answer.get(i) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int N = 4;
// Function call
printArray(N);
}
}
// This code is contributed by phasing.
Python3
# Python code to implement the approach M = 100001 primes = [0]*(M + 1) # Function to form an array such that # pairwise gcd of all elements is not 1 # and gcd of whole sequence is 1 def printArrayint(N): # Such sequence is not possible for N=2 if N == 2: print(-1) return # storing primes upto M using sieve for i in range(M): primes[i] = 1 primes[0] = 0 primes[1] = 0 i = 2 while i * i <= M: if primes[i] == 1: j = i*i while j <= M: primes[j] = 0 j += i i += 1 # Storing first N primes in vector v v = [] for i in range(M): if len(v) < N and primes[i] == 1: v.append(i) # Calculating product of # first N prime numbers product = 1 answer = [] for it in v: product *= it # Calculating answer sequence for i in range(N): num = product // v[i] answer.append(num) # Printing the answer for i in range(N): print(answer[i], end=" ") # Driver Code if __name__ == "__main__": N = 4 printArrayint(N) # This code is contributed by amnindersingh1414.
C#
// C# code to implement the approach
using System;
using System.Collections;
class GFG {
static int M = 100001;
static int[] primes = new int[M + 1];
// Function to form an array such that
// pairwise gcd of all elements is not 1
// and gcd of whole sequence is 1
static void printArray(int N)
{
// Such sequence is not possible for N=2
if (N == 2) {
Console.WriteLine(-1);
return;
}
// storing primes upto M using sieve
for (int i = 0; i < M; i++)
primes[i] = 1;
primes[0] = 0;
primes[1] = 0;
for (int i = 2; i * i <= M; i++) {
if (primes[i] == 1) {
for (int j = i * i; j <= M; j += i) {
primes[j] = 0;
}
}
}
// Storing first N primes in vector v
ArrayList v = new ArrayList();
for (int i = 0; i < M; i++) {
if (v.Count < N && primes[i] == 1) {
v.Add(i);
}
}
// Calculating product of
// first N prime numbers
int product = 1;
ArrayList answer = new ArrayList();
foreach(int it in v) { product *= (int)it; }
// Calculating answer sequence
for (int i = 0; i < N; i++) {
int num = product / (int)v[i];
answer.Add(num);
}
// Printing the answer
for (int i = 0; i < N; i++) {
Console.Write(answer[i] + " ");
}
}
// Driver Code
public static void Main()
{
int N = 4;
// Function call
printArray(N);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
let M = 100001;
let primes = new Array(M + 1);
// Function to form an array such that
// pairwise gcd of all elements is not 1
// and gcd of whole sequence is 1
function printArray(N)
{
// Such sequence is not possible for N=2
if (N == 2) {
document.write(-1 + "<br>")
return;
}
// storing primes upto M using sieve
for (let i = 0; i < M; i++)
primes[i] = 1;
primes[0] = 0;
primes[1] = 0;
for (let i = 2; i * i <= M; i++) {
if (primes[i] == 1) {
for (let j = i * i; j <= M;
j += i) {
primes[j] = 0;
}
}
}
// Storing first N primes in vector v
let v = [];
for (let i = 0; i < M; i++) {
if (v.length < N
&& primes[i] == 1) {
v.push(i);
}
}
// Calculating product of
// first N prime numbers
let product = 1;
let answer = [];
for (let it of v) {
product *= it;
}
// Calculating answer sequence
for (let i = 0; i < N; i++) {
let num = Math.floor(product / v[i]);
answer.push(num);
}
// Printing the answer
for (let i = 0; i < N; i++) {
document.write(answer[i] + " ")
}
}
// Driver Code
let N = 4;
// Function call
printArray(N);
// This code is contributed by Potta Lokesh
</script>
Producción
105 70 42 30
Complejidad de tiempo: O(M*(log(logM))) donde M es un número positivo grande [aquí, 100000]
Espacio auxiliar: O(M)
Mejor enfoque: el enfoque anterior fallará para valores más grandes de N, ya que no se puede almacenar el producto de más de 15 números primos. Esto se puede evitar en base a la siguiente observación:
Fija los tres primeros números distintos con todos los productos posibles formados tomando dos entre los tres primeros primos (digamos que los números formados son X, Y y Z).
Luego, para los siguientes elementos, siga multiplicando cualquiera (digamos X ) por uno de los números primos (digamos que se convierte en X’ ) y cambie X a X’.Como el MCD de X, Y y Z es 1, el MCD general será uno, pero no habrá dos elementos coprimos entre sí.
Para su propia conveniencia use los primeros 3 números primos 2, 3, 5 y haga los primeros 3 números como 10, 15, 6 y los otros multiplicándolos por 2, es decir, 12, 24, 48, . . .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for above approach
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
// Function to form an array such that
// pairwise gcd of all elements is not 1
// and gcd of whole sequence is 1
void printArray(int N)
{
if (N == 1) {
cout << 2 << endl;
}
// Such sequence is not possible for N = 2
if (N == 2) {
cout << -1 << endl;
return;
}
int ans[N];
// Initializing initial 3 terms
// of the sequence
ans[0] = 10, ans[1] = 15, ans[2] = 6;
// Calculating next terms of the sequence
// by multiplying previous terms by 2
for (int i = 3; i < N; i++) {
ans[i] = 2LL * ans[i - 1];
}
// Printing the final sequence
for (int i = 0; i < N; i++) {
cout << ans[i] << " ";
}
}
// Driver Code
int32_t main()
{
int N = 4;
// Function call
printArray(N);
return 0;
}
Java
// JAVA code for above approach
import java.util.*;
class GFG {
// Function to form an array such that
// pairwise gcd of all elements is not 1
// and gcd of whole sequence is 1
public static void printArray(int N)
{
if (N == 1) {
System.out.println(2);
}
// Such sequence is not possible for N = 2
if (N == 2) {
System.out.println(-1);
return;
}
int ans[] = new int[N];
// Initializing initial 3 terms
// of the sequence
ans[0] = 10;
ans[1] = 15;
ans[2] = 6;
// Calculating next terms of the sequence
// by multiplying previous terms by 2
for (int i = 3; i < N; i++) {
ans[i] = 2 * ans[i - 1];
}
// Printing the final sequence
for (int i = 0; i < N; i++) {
System.out.print(ans[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int N = 4;
// Function call
printArray(N);
}
}
// This code is contributed by Taranpreet
Python3
# Python code for above approach # Function to form an array such that # pairwise gcd of all elements is not 1 # and gcd of whole sequence is 1 def printArray(N): if (N == 1): print(2) # Such sequence is not possible for N = 2 if (N == 2): print(-1) return ans = [0]*N # Initializing initial 3 terms # of the sequence ans[0] = 10 ans[1] = 15 ans[2] = 6 # Calculating next terms of the sequence # by multiplying previous terms by 2 for i in range(3, N): ans[i] = 2 * ans[i - 1] # Printing the final sequence for i in range(N): print(ans[i], end=" ") # Driver Code if __name__ == '__main__': N = 4 printArray(N) # This code is contributed by amnindersingh1414.
C#
// C# code to implement the above approach
using System;
class GFG
{
// Function to form an array such that
// pairwise gcd of all elements is not 1
// and gcd of whole sequence is 1
public static void printArray(int N)
{
if (N == 1) {
Console.Write(2);
}
// Such sequence is not possible for N = 2
if (N == 2) {
Console.Write(-1);
return;
}
int[] ans = new int[N];
// Initializing initial 3 terms
// of the sequence
ans[0] = 10;
ans[1] = 15;
ans[2] = 6;
// Calculating next terms of the sequence
// by multiplying previous terms by 2
for (int i = 3; i < N; i++) {
ans[i] = 2 * ans[i - 1];
}
// Printing the final sequence
for (int i = 0; i < N; i++) {
Console.Write(ans[i] + " ");
}
}
// Driver code
public static void Main()
{
int N = 4;
// Function call
printArray(N);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript code for above approach
// Function to form an array such that
// pairwise gcd of all elements is not 1
// and gcd of whole sequence is 1
function printArray( N)
{
if (N == 1) {
document.write(2);
}
// Such sequence is not possible for N = 2
if (N == 2) {
document.write(-1);
return;
}
let ans = new Array(N);
// Initializing initial 3 terms
// of the sequence
ans[0] = 10;
ans[1] = 15;
ans[2] = 6;
// Calculating next terms of the sequence
// by multiplying previous terms by 2
for (let i = 3; i < N; i++) {
ans[i] = 2 * ans[i - 1];
}
// Printing the final sequence
for (let i = 0; i < N; i++) {
document.write(ans[i] + " ");
}
}
// Driver Code
let N = 4;
// Function call
printArray(N);
// This code is contributed by jana_sayantan.
</script>
Producción
10 15 6 12
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kamabokogonpachiro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA