Cuente números enteros en un rango que son divisibles por su valor de euler totient

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:

*** 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:
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: 
 

\phi(n) = n * (1 - \frac{1}{p_1}) * (1 - \frac{1}{p_2}) * ... * (1 - \frac{1}{p_k})

Reordenando los términos, obtenemos: 
 

\frac{n}{\phi(n)} = \frac{p_1 * p_2 * ... * p_k}{(p_1 - 1) * (p_2 -1) * ... * (p_k -1)}

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *