Número de resultados pares e impares para cada valor de x en el rango [mín., máx.] después de realizar N pasos

Dado un número N y el rango mínimo y máximo. Dados N valores de a y b respectivamente. La tarea es contar el número de resultados pares/impares después de realizar una serie de N operaciones como se describe a continuación.
En cada paso, calcula: 

y _norte = un _norte y _norte-1 + segundo _norte . 
 

Explicación:  

• Paso 1: y ₁ = a ₁ x + b ₁
• Paso 2: y ₂ = un ₂ y ₁ + _{segundo 2} => y ₂ = un ₂ un ₁ x + un _{2 segundo} 1 ₊ segundo ₂
• Paso 3: y ₃ = a ₃ y ₂ + b ₃ => y ₃ = a ₃ a ₂ a ₁ x + a ₃ a ₂ b ₁ + a ₃ b ₂ + b ₃
• Paso n: y _n = a _n y _n-1 + b _n

Para obtener los resultados finales, tome los valores de y ₀ como cada valor en el rango [min, mix]. Para simplificar, asumimos que el valor de y ₀ es x y reemplazamos x con todos los valores posibles en el rango [min, max] en la ecuación final para calcular los resultados.

Ejemplos:  

Input: n = 2,  min = 1, max = 4 
       a = 1, b = 2 
       a = 3, b = 4 
Output: even = 2, odd = 2. 

Step1: y = 1x + 2 = x+2 
Step2: y =  3(x+2) + 4 = 3x + 10 
Putting all values of in range [1, 4], 
2 odd values and 2 even values are obtained. 

Input: n = 1, min = 4, max = 60
       a= 1, b = 2

Output: even = 29, odd = 28

Un enfoque ingenuo será almacenar los valores de a y b en una array y calcular el resultado final para cada número en el rango especificado. Si el resultado es par, se incrementa el conteo de pares. De lo contrario, se incrementa el recuento de impares.

Un enfoque eficiente que se usa aquí es el concepto básico de que el producto de dos números es par si cualquiera de los números es par, de lo contrario impar, y la suma de dos números es par solo si ambos números son pares. Aquí se ve que en cada paso se multiplica un número por x y se suma otra constante al producto. La tarea es comprobar si el resultado es par o impar. En el último paso del cálculo, comprueba que si a ₁ a ₂ a ₃ …a _n es par/impar, y a ₂ a ₃ …a _n b ₁ + a ₃ a ₄ …a _n b ₂ + … + b _nes par/impar. Comprobando si a ₁ a ₂ a ₃ …a _n es par/impar: 
Si alguna _ai es par, el producto siempre será par, de lo contrario será impar. Comprobando si a ₂ a ₃ …a _n b ₁ + a ₃ a ₄ …a _n b ₂ + … + b _n es par/impar: 

La siguiente tabla explica todas las diversas posibilidades para los coeficientes:  

La siguiente tabla explica todas las diversas posibilidades para y = ax + b:
 

En lugar de recorrer todos los números en el rango [min, max], divídalo en dos partes para verificar si el número en el rango es par o impar, ya que todas las entradas pares tienen el mismo resultado y todas las entradas impares tienen el mismo resultado. mismo resultado. Por lo tanto, verifique un caso y multiplíquelo por el número de pares e impares en el rango. 

Se lleva a cabo el cálculo anterior y se comprueba el coeficiente de x en el último paso.  

• Si es par, entonces apar es verdadero, de lo contrario falso.
• Si la constante es par, entonces beven es verdadero, de lo contrario, falso.
• El coeficiente de x es par de cualquier valor de a es par en cualquier capa.
• El término constante después de la última capa, si se ejecuta, se verifica con la ayuda del valor de beven y actual a y b.

Con la ayuda de la tabla anterior (la primera), se prueba la constante en cada capa y el valor de beven se actualiza en consecuencia. 

Suponga que x es par, el valor de par e impar se inicializa. 

1. Si x es par, entonces ax siempre será par, independientemente de a. Por tanto, dependiendo del valor del término constante, el resultado será par o impar.
2. Si la constante es par, entonces el resultado es par, por lo tanto, par se inicializa con el número de par en el rango dado (max/2 – (min-1)/2) y impar se inicializa con cero.
3. Si la constante es impar, entonces el resultado es impar, por lo que impar se inicializa con el número de pares en el rango dado (max/2 – (min-1)/2) y par se inicializa con cero.

Suponiendo que x es impar, se actualiza el valor de par e impar.  

1. Si a es impar, ax es impar. Si a es par, ax es par.
2. Si ax y constante, ambos son impares o ax y constante, ambos son pares, entonces el resultado es par, por lo tanto, par se incrementa por el número de impares en el rango dado (max – min + 1 – número de pares) .
3. Si ax es par y la constante es impar o ax es impar y la constante es impar, entonces el resultado es impar, por lo que el número de impares se incrementa por el número de impares en el rango dado (max – min + 1 – número de pares) .

A continuación se muestra la implementación del enfoque anterior:  

// C++ program to print
// Number of odd/even results for
// every value of x in range [min, end]
// after performing N steps
#include <bits/stdc++.h>
using namespace std;
 
// Function that prints the
// number of odd and even results
void count_even_odd(int min, int max, int steps[][2])
{
    int a, b, even, odd;
 
    // If constant at layer i is even, beven is true,
    // otherwise false. If the coefficient of x at
    // layer i is even, aeven is true, otherwise false.
    bool beven = true, aeven = false;
    int n = 2;
    for (int i = 0; i < n; i++) {
 
        a = steps[i][0], b = steps[i][1];
 
        // If any of the coefficients at any layer is found
        // to be even, then the product of all the
        // coefficients will always be even.
 
        if (!(aeven || a & 1))
            aeven = true;
 
        // Checking whether the constant added after all
        // layers is even or odd.
 
        if (beven) {
            if (b & 1)
                beven = false;
        }
        else if (!(a & 1)) {
            if (!(b & 1))
                beven = true;
        }
        else {
            if (b & 1)
                beven = true;
        }
    }
 
    // Counting the number of even and odd.
 
    // Assuming input x is even.
    if (beven) {
        even = (int)max / 2 - (int)(min - 1) / 2;
        odd = 0;
    }
    else {
        even = (int)max / 2 - (int)(min - 1) / 2;
        odd = 0;
    }
 
    // Assuming input x is odd.
    if (!(beven ^ aeven))
        even += max - min + 1 - (int)max / 2
                + (int)(min - 1) / 2;
    else
        odd += max - min + 1 - (int)max / 2
               + (int)(min - 1) / 2;
 
    // Displaying the counts.
    cout << "even = " << even << ", odd = " << odd << endl;
}
 
// Driver Code
int main()
{
    int min = 1, max = 4;
    int steps[][2] = { { 1, 2 },
                       { 3, 4 } };
 
    count_even_odd(min, max, steps);
    return 0;
}

// Java program to print
// Number of odd/even
// results for every value
// of x in range [min, end]
// after performing N steps
import java.io.*;
 
class GFG
{
 
// Function that prints
// the number of odd and
// even results
static void count_even_odd(int min,
                           int max,
                           int steps[][])
{
    int a, b, even, odd;
 
    // If constant at layer i
    // is even, beven is true,
    // otherwise false. If the
    // coefficient of x at layer
    // i is even, aeven is true,
    // otherwise false.
    boolean beven = true,
            aeven = false;
    int n = 2;
    for (int i = 0; i < n; i++)
    {
 
        a = steps[i][0];
        b = steps[i][1];
 
        // If any of the coefficients
        // at any layer is found to be
        // even, then the product of
        // all the coefficients will
        // always be even.
        if (!(aeven || (a & 1) > 0))
            aeven = true;
 
        // Checking whether the
        // constant added after all
        // layers is even or odd.
        if (beven)
        {
            if ((b & 1) > 0)
                beven = false;
        }
        else if (!((a & 1) > 0))
        {
            if (!((b & 1) > 0))
                beven = true;
        }
        else
        {
            if ((b & 1) > 0)
                beven = true;
        }
    }
 
    // Counting the number
    // of even and odd.
 
    // Assuming input x is even.
    if (beven)
    {
        even = (int)max / 2 -
               (int)(min - 1) / 2;
        odd = 0;
    }
    else
    {
        even = (int)max / 2 -
               (int)(min - 1) / 2;
        odd = 0;
    }
 
    // Assuming input x is odd.
    if (!(beven ^ aeven))
        even += max - min + 1 -
                (int)max / 2 +
                (int)(min - 1) / 2;
    else
        odd += max - min + 1 -
               (int)max / 2 +
               (int)(min - 1) / 2;
 
    // Displaying the counts.
    System.out.print("even = " + even +
                     ", odd = " + odd);
}
 
// Driver Code
public static void main (String[] args)
{
    int min = 1, max = 4;
    int steps[][] = {{1, 2},
                     {3, 4}};
 
    count_even_odd(min, max, steps);
}
}
 
// This code is contributed
// by anuj_67.

# Python3 program to print
# Number of odd/even results
# for every value of x in
# range [min, end] after
# performing N steps
 
# Function that prints
# the number of odd
# and even results
def count_even_odd(min, max, steps):
  
    # If constant at layer i
    # is even, beven is True,
    # otherwise False. If
    # the coefficient of x at
    # layer i is even, aeven
    # is True, otherwise False.
    beven = True
    aeven = False
    n = 2
    for i in range(0, n) :
        a = steps[i][0]
        b = steps[i][1]
  
        # If any of the coefficients
        # at any layer is found to
        # be even, then the product
        # of all the coefficients
        # will always be even.
        if (not(aeven or a & 1)):
            aeven = True
  
        # Checking whether the
        # constant added after all
        # layers is even or odd.
        if (beven) :
            if (b & 1):
                beven = False
          
        elif (not(a & 1)) :
            if (not(b & 1)):
                beven = True
          
        else :
            if (b & 1):
                beven = True
          
    # Counting the number
    # of even and odd.
  
    # Assuming input x is even.
    if (beven):
        even = (int(max / 2) -
                int((min - 1) / 2))
        odd = 0
      
    else :
        even = (int(max / 2) -
                int((min - 1) / 2))
        odd = 0
  
    # Assuming input x is odd.
    if (not(beven ^ aeven)):
        even += (max - min + 1 -
             int(max / 2) + int((min - 1) / 2))
    else:
        odd += (max - min + 1 -
            int(max / 2) + int((min - 1) / 2))
  
    # Displaying the counts.
    print("even = " , even ,
          ", odd = " , odd, sep = "")
  
# Driver Code
min = 1
max = 4
steps = [[1, 2],[3, 4]]
count_even_odd(min, max, steps)
 
# This code is contributed
# by Smitha

// C# program to print
// Number of odd/even
// results for every value
// of x in range [min, end]
// after performing N steps
using System;
 
class GFG
{
 
// Function that prints
// the number of odd and
// even results
static void count_even_odd(int min,
                           int max,
                           int [,]steps)
{
    int a, b, even, odd;
 
    // If constant at layer i
    // is even, beven is true,
    // otherwise false. If the
    // coefficient of x at layer
    // i is even, aeven is true,
    // otherwise false.
    bool beven = true,
         aeven = false;
    int n = 2;
    for (int i = 0; i < n; i++)
    {
 
        a = steps[i, 0];
        b = steps[i, 1];
 
        // If any of the coefficients
        // at any layer is found
        // to be even, then the
        // product of all the
        // coefficients will always
        // be even.
        if (!(aeven || (a & 1) > 0))
            aeven = true;
 
        // Checking whether the
        // constant added after all
        // layers is even or odd.
        if (beven)
        {
            if ((b & 1) > 0)
                beven = false;
        }
        else if (!((a & 1) > 0))
        {
            if (!((b & 1) > 0))
                beven = true;
        }
        else
        {
            if ((b & 1) > 0)
                beven = true;
        }
    }
 
    // Counting the number
    // of even and odd.
 
    // Assuming input
    // x is even.
    if (beven)
    {
        even = (int)max / 2 -
               (int)(min - 1) / 2;
        odd = 0;
    }
    else
    {
        even = (int)max / 2 -
            (int)(min - 1) / 2;
        odd = 0;
    }
 
    // Assuming input
    // x is odd.
    if (!(beven ^ aeven))
        even += max - min + 1 -
                 (int)max / 2 +
                (int)(min - 1) / 2;
    else
        odd += max - min + 1 -
            (int)max / 2 +
            (int)(min - 1) / 2;
 
    // Displaying the counts.
    Console.Write("even = " + even +
                  ", odd = " + odd);
}
 
// Driver Code
public static void Main ()
{
    int min = 1, max = 4;
    int [,]steps = {{1, 2},
                    {3, 4}};
 
    count_even_odd(min, max, steps);
}
}
 
// This code is contributed
// by anuj_67.

<?php
// PHP program to print Number of
// odd/even results for every value
// of x in range [min, end] after
// performing N steps
 
// Function that prints the
// number of odd and even results
function count_even_odd($min, $max, $steps)
{
    // If constant at layer i is even,
    // beven is true, otherwise false.
    // If the coefficient of x at
    // layer i is even, aeven is true,
    // otherwise false.
    $beven = true;
    $aeven = false;
    $n = 2;
    for ($i = 0; $i < $n; $i++)
    {
 
        $a = $steps[$i][0];
        $b = $steps[$i][1];
 
        // If any of the coefficients at
        // any layer is found to be even,
        // then the product of all the
        // coefficients will always be even.
        if (!($aeven || $a & 1))
            $aeven = true;
 
        // Checking whether the constant
        // added after all layers is even or odd.
 
        if ($beven)
        {
            if ($b & 1)
                $beven = false;
        }
        else if (!($a & 1))
        {
            if (!($b & 1))
                $beven = true;
        }
        else
        {
            if ($b & 1)
                $beven = true;
        }
    }
 
    // Counting the number of even and odd.
 
    // Assuming input x is even.
    if ($beven)
    {
        $even = (int)$max / 2 - (int)($min - 1) / 2;
        $odd = 0;
    }
    else
    {
        $even = (int)$max / 2 - (int)($min - 1) / 2;
        $odd = 0;
    }
 
    // Assuming input x is odd.
    if (!($beven ^ $aeven))
        $even += $max - $min + 1 - (int)$max / 2 +
                                   (int)($min - 1) / 2;
    else
        $odd += $max - $min + 1 - (int)$max / 2 +
                                  (int)($min - 1) / 2;
 
    // Displaying the counts.
    echo "even = " , $even,
         ", odd = ", $odd, "\n";
}
 
// Driver Code
$min = 1;
$max = 4;
$steps = array( array(1, 2 ),
                array(3, 4 ));
 
count_even_odd($min, $max, $steps);
 
// This code is contributed
// by Ajit Deshpal
?>

<script>
 
// Javascript program to print
// Number of odd/even
// results for every value
// of x in range [min, end]
// after performing N steps
 
// Function that prints
// the number of odd and
// even results
function count_even_odd(min, max, steps)
{
    var a, b, even, odd;
     
    // If constant at layer i
    // is even, beven is true,
    // otherwise false. If the
    // coefficient of x at layer
    // i is even, aeven is true,
    // otherwise false.
    var beven = true, aeven = false;
    var n = 2;
     
    for(i = 0; i < n; i++)
    {
        a = steps[i][0];
        b = steps[i][1];
 
        // If any of the coefficients
        // at any layer is found to be
        // even, then the product of
        // all the coefficients will
        // always be even.
        if (!(aeven || (a & 1) > 0))
            aeven = true;
 
        // Checking whether the
        // constant added after all
        // layers is even or odd.
        if (beven)
        {
            if ((b & 1) > 0)
                beven = false;
        }
        else if (!((a & 1) > 0))
        {
            if (!((b & 1) > 0))
                beven = true;
        }
        else
        {
            if ((b & 1) > 0)
                beven = true;
        }
    }
 
    // Counting the number
    // of even and odd.
 
    // Assuming input x is even.
    if (beven)
    {
        even = parseInt(max / 2) -
               parseInt((min - 1) / 2);
        odd = 0;
    }
    else
    {
        even = parseInt(max / 2) -
               parseInt((min - 1) / 2);
        odd = 0;
    }
 
    // Assuming input x is odd.
    if (!(beven ^ aeven))
        even += max - min + 1 - parseInt(max / 2) +
                                parseInt((min - 1) / 2);
    else
        odd += max - min + 1 - parseInt(max / 2) +
                               parseInt((min - 1) / 2);
 
    // Displaying the counts.
    document.write("even = " + even + ", odd = " + odd);
}
 
// Driver Code
var min = 1, max = 4;
var steps = [ [ 1, 2 ], [ 3, 4 ] ];
 
count_even_odd(min, max, steps);
 
// This code is contributed by aashish1995
 
</script>

even = 2, odd = 2

Complejidad temporal: O(N) donde N es el número dado de operaciones.
Espacio Auxiliar: O(1)