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>
Producción:
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