Dados 2 números enteros L y R , la tarea es encontrar el número de números enteros en el rango [L, R] tales que sean completamente divisibles por su valor de Euler totient.
Ejemplos:
Entrada: L = 2, R = 3
Salida: 1*** QuickLaTeX no puede compilar la fórmula: *** Mensaje de error: Error: nada que mostrar, la fórmula está vacía(2) = 2 => 2 %
*** QuickLaTeX no puede compilar la fórmula: *** Mensaje de error: Error: nada que mostrar, la fórmula está vacía(2) = 0
*** QuickLaTeX no puede compilar la fórmula: *** Mensaje de error: Error: nada que mostrar, la fórmula está vacía(3) = 2 => 3 %
*** QuickLaTeX no puede compilar la fórmula: *** Mensaje de error: Error: nada que mostrar, la fórmula está vacía(3) = 1
Por lo tanto, 2 satisface la condición.
Entrada: L = 12, R = 21
Salida: 3
Solo 12, 16 y 18 cumplen la condición.
Enfoque: Sabemos que la función totient de Euler de un número se da de la siguiente manera:
Reordenando los términos, obtenemos:
Si observamos de cerca la RHS, observamos que solo 2 y 3 son los primos que satisfacen n %
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
= 0 . Esto se debe a que para los números primos p 1 = 2 y p 2 = 3, p 1 – 1 = 1 y p 2 – 1 = 2 . Por lo tanto, solo los números de la forma 2 p 3 q donde p >= 1 y q >= 0 deben contarse mientras se encuentran en el rango [L, R] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach. #include <bits/stdc++.h> #define ll long long using namespace std; // Function to return a^n ll power(ll a, ll n) { if (n == 0) return 1; ll p = power(a, n / 2); p = p * p; if (n & 1) p = p * a; return p; } // Function to return count of integers // that satisfy n % phi(n) = 0 int countIntegers(ll l, ll r) { ll ans = 0, i = 1; ll v = power(2, i); while (v <= r) { while (v <= r) { if (v >= l) ans++; v = v * 3; } i++; v = power(2, i); } if (l == 1) ans++; return ans; } // Driver Code int main() { ll l = 12, r = 21; cout << countIntegers(l, r); return 0; }
Java
// Java implementation of the above approach. class GFG { // Function to return a^n static long power(long a, long n) { if (n == 0) return 1; long p = power(a, n / 2); p = p * p; if (n%2== 1) p = p * a; return p; } // Function to return count of integers // that satisfy n % phi(n) = 0 static int countIntegers(long l, long r) { long ans = 0, i = 1; long v = power(2, i); while (v <= r) { while (v <= r) { if (v >= l) ans++; v = v * 3; } i++; v = power(2, i); } if (l == 1) ans++; return (int) ans; } // Driver Code public static void main(String[] args) { long l = 12, r = 21; System.out.println(countIntegers(l, r)); } } // This code contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to return a^n def power(a, n): if n == 0: return 1 p = power(a, n // 2) p = p * p if n & 1: p = p * a return p # Function to return count of integers # that satisfy n % phi(n) = 0 def countIntegers(l, r): ans, i = 0, 1 v = power(2, i) while v <= r: while v <= r: if v >= l: ans += 1 v = v * 3 i += 1 v = power(2, i) if l == 1: ans += 1 return ans # Driver Code if __name__ == "__main__": l, r = 12, 21 print(countIntegers(l, r)) # This code is contributed # by Rituraj Jain
C#
// C# implementation of the above approach. using System; class GFG { // Function to return a^n static long power(long a, long n) { if (n == 0) return 1; long p = power(a, n / 2); p = p * p; if (n % 2 == 1) p = p * a; return p; } // Function to return count of integers // that satisfy n % phi(n) = 0 static int countIntegers(long l, long r) { long ans = 0, i = 1; long v = power(2, i); while (v <= r) { while (v <= r) { if (v >= l) ans++; v = v * 3; } i++; v = power(2, i); } if (l == 1) ans++; return (int) ans; } // Driver Code public static void Main() { long l = 12, r = 21; Console.WriteLine(countIntegers(l, r)); } } /* This code contributed by PrinciRaj1992 */
PHP
<?php // PHP implementation of the above approach // Function to return a^n function power($a, $n) { if ($n == 0) return 1; $p = power($a, $n / 2); $p = $p * $p; if ($n & 1) $p = $p * $a; return $p; } // Function to return count of integers // that satisfy n % phi(n) = 0 function countIntegers($l, $r) { $ans = 0 ; $i = 1; $v = power(2, $i); while ($v <= $r) { while ($v <= $r) { if ($v >= $l) $ans++; $v = $v * 3; } $i++; $v = power(2, $i); } if ($l == 1) $ans++; return $ans; } // Driver Code $l = 12; $r = 21; echo countIntegers($l, $r); // This code is contributed by Ryuga ?>
Javascript
<script> // JavaScript implementation of the above approach. // Function to return a^n function power(a , n) { if (n == 0) return 1; var p = power(a, parseInt(n / 2)); p = p * p; if (n % 2 == 1) p = p * a; return p; } // Function to return count of integers // that satisfy n % phi(n) = 0 function countIntegers(l , r) { var ans = 0, i = 1; var v = power(2, i); while (v <= r) { while (v <= r) { if (v >= l) ans++; v = v * 3; } i++; v = power(2, i); } if (l == 1) ans++; return parseInt( ans); } // Driver Code var l = 12, r = 21; document.write(countIntegers(l, r)); // This code contributed by Rajput-Ji </script>
3
Publicación traducida automáticamente
Artículo escrito por rohan23chhabra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA