Dados dos enteros N y K , la tarea es encontrar la permutación P de los primeros N números naturales tal que haya exactamente K elementos que satisfagan la condición GCD(P[i], i) > 1 para todo 1 ≤ i ≤ N .
Ejemplos:
Entrada: N = 3, K = 1
Salida: 2 1 3
MCD(P[1], 1) = MCD(2, 1) = 1
MCD(P[2], 2) = MCD(1, 2) = 1
MCD(P[3], 3) = MCD(3, 3) = 3
Hay exactamente 1 elemento tal que MCD(P[i], i) > 1
Entrada: N = 5, K = 2
Salida: 3 1 2 4 5
Enfoque: Mantenga los últimos elementos K en su lugar. El resto de los elementos se mueven de manera que el elemento i se coloca en (i + 1) la posición y el elemento (N – K) se mantiene en la posición 1 porque mcd(x, x + 1) = 1 .
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 find permutation(p) of first N // natural numbers such that there are exactly K // elements of permutation such that GCD(p[i], i)>1 void Permutation(int n, int k) { int p[n + 1]; // First place all the numbers // in their respective places for (int i = 1; i <= n; i++) p[i] = i; // Modify for first n-k integers for (int i = 1; i < n - k; i++) p[i + 1] = i; // In first index place n-k p[1] = n - k; // Print the permutation for (int i = 1; i <= n; i++) cout << p[i] << " "; } // Driver code int main() { int n = 5, k = 2; Permutation(n, k); return 0; }
Java
// Java implementation of the approach class GFG { // Function to find permutation(p) of first N // natural numbers such that there are exactly K // elements of permutation such that GCD(p[i], i)>1 static void Permutation(int n, int k) { int[] p = new int[n + 1]; // First place all the numbers // in their respective places for (int i = 1; i <= n; i++) p[i] = i; // Modify for first n-k integers for (int i = 1; i < n - k; i++) p[i + 1] = i; // In first index place n-k p[1] = n - k; // Print the permutation for (int i = 1; i <= n; i++) System.out.print(p[i] + " "); } // Driver code public static void main(String[] args) { int n = 5, k = 2; Permutation(n, k); } } // This code is contributed by Naman_Garg
Python3
# Python 3 implementation of the approach # Function to find permutation(p) # of first N natural numbers such that # there are exactly K elements of # permutation such that GCD(p[i], i)>1 def Permutation(n, k): p = [0 for i in range(n + 1)] # First place all the numbers # in their respective places for i in range(1, n + 1): p[i] = i # Modify for first n-k integers for i in range(1, n - k): p[i + 1] = i # In first index place n-k p[1] = n - k # Print the permutation for i in range(1, n + 1): print(p[i], end = " ") # Driver code if __name__ == '__main__': n = 5 k = 2 Permutation(n, k) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach using System; class GFG { // Function to find permutation(p) of first N // natural numbers such that there are exactly K // elements of permutation such that GCD(p[i], i)>1 static void Permutation(int n, int k) { int[] p = new int[n + 1]; // First place all the numbers // in their respective places for (int i = 1; i <= n; i++) p[i] = i; // Modify for first n-k integers for (int i = 1; i < n - k; i++) p[i + 1] = i; // In first index place n-k p[1] = n - k; // Print the permutation for (int i = 1; i <= n; i++) Console.Write(p[i] + " "); } // Driver code static public void Main () { int n = 5, k = 2; Permutation(n, k); } } // This code is contributed by ajit.
PHP
<?php // PHP implementation of the approach // Function to find permutation(p) of first N // natural numbers such that there are exactly K // elements of permutation such that GCD(p[i], i)>1 function Permutation($n, $k) { $p = array(); // First place all the numbers // in their respective places for ($i = 1; $i <= $n; $i++) $p[$i] = $i; // Modify for first n-k integers for ($i = 1; $i < $n - $k; $i++) $p[$i + 1] = $i; // In first index place n-k $p[1] = $n - $k; // Print the permutation for ($i = 1; $i <= $n; $i++) echo $p[$i], " "; } // Driver code $n = 5; $k = 2; Permutation($n, $k); // This code is contributed by AnkitRai01 ?>
Javascript
<script> //Javascript implementation of the approach // Function to find permutation(p) of first N // natural numbers such that there are exactly K // elements of permutation such that GCD(p[i], i)>1 function Permutation(n, k) { let p = new Array(n + 1); // First place all the numbers // in their respective places for (let i = 1; i <= n; i++) p[i] = i; // Modify for first n-k integers for (let i = 1; i < n - k; i++) p[i + 1] = i; // In first index place n-k p[1] = n - k; // Print the permutation for (let i = 1; i <= n; i++) document.write(p[i] + " "); } // Driver code let n = 5, k = 2; Permutation(n, k); // This code is contributed by Mayank Tyagi </script>
3 1 2 4 5
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA