Dado un entero positivo N , la tarea es generar una array tal que la suma de la Función Euler Totient de cada elemento sea igual a N .
Ejemplos:
Entrada: N = 6
Salida: 1 6 2 3Entrada: N = 12
Salida: 1 12 2 6 3 4
Enfoque: El problema dado se puede resolver con base en la propiedad de la suma del divisor de la función Euler Totient , es decir,
- La Función Euler Totient de un número N < es el número de enteros de 1 a N que da GCD(i, N) como 1 y un número N se puede representar como la suma de los valores de la Función Euler Totient de todos los divisores de N .
- Por lo tanto, la idea es encontrar los divisores del número dado N como el arreglo resultante .
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 construct the array such // the sum of values of Euler Totient // functions of all array elements is N void constructArray(int N) { // Stores the resultant array vector<int> ans; // Find divisors in sqrt(N) for (int i = 1; i * i <= N; i++) { // If N is divisible by i if (N % i == 0) { // Push the current divisor ans.push_back(i); // If N is not a // perfect square if (N != (i * i)) { // Push the second divisor ans.push_back(N / i); } } } // Print the resultant array for (auto it : ans) { cout << it << " "; } } // Driver Code int main() { int N = 12; // Function Call constructArray(N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to construct the array such // the sum of values of Euler Totient // functions of all array elements is N static void constructArray(int N) { // Stores the resultant array ArrayList<Integer> ans = new ArrayList<Integer>(); // Find divisors in sqrt(N) for(int i = 1; i * i <= N; i++) { // If N is divisible by i if (N % i == 0) { // Push the current divisor ans.add(i); // If N is not a // perfect square if (N != (i * i)) { // Push the second divisor ans.add(N / i); } } } // Print the resultant array for(int it : ans) { System.out.print(it + " "); } } // Driver Code public static void main(String[] args) { int N = 12; // Function Call constructArray(N); } } // This code is contributed by splevel62
Python3
# Python3 program for the above approach from math import sqrt # Function to construct the array such # the sum of values of Euler Totient # functions of all array elements is N def constructArray(N): # Stores the resultant array ans = [] # Find divisors in sqrt(N) for i in range(1, int(sqrt(N)) + 1, 1): # If N is divisible by i if (N % i == 0): # Push the current divisor ans.append(i) # If N is not a # perfect square if (N != (i * i)): # Push the second divisor ans.append(N / i) # Print the resultant array for it in ans: print(int(it), end = " ") # Driver Code if __name__ == '__main__': N = 12 # Function Call constructArray(N) # This code is contributed by ipg2016107
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to construct the array such // the sum of values of Euler Totient // functions of all array elements is N static void constructArray(int N) { // Stores the resultant array List<int> ans = new List<int>(); // Find divisors in sqrt(N) for(int i = 1; i * i <= N; i++) { // If N is divisible by i if (N % i == 0) { // Push the current divisor ans.Add(i); // If N is not a // perfect square if (N != (i * i)) { // Push the second divisor ans.Add(N / i); } } } // Print the resultant array foreach(int it in ans) { Console.Write(it + " "); } } // Driver Code public static void Main() { int N = 12; // Function Call constructArray(N); } } // This code is contributed by ukasp
Javascript
<script> // javascript program for the above approach // Function to construct the array such // the sum of values of Euler Totient // functions of all array elements is N function constructArray(N) { // Stores the resultant array var ans = []; // Find divisors in sqrt(N) for(var i = 1; i * i <= N; i++) { // If N is divisible by i if (N % i == 0) { // Push the current divisor ans.push(i); // If N is not a // perfect square if (N != (i * i)) { // Push the second divisor ans.push(N / i); } } } // Print the resultant array document.write(ans); } // Driver Code var N = 12; // Function Call constructArray(N); // This code contributed by shikhasingrajput </script>
Producción:
1 12 2 6 3 4
Complejidad temporal: O(√N)
Espacio auxiliar: O(N)