Valor de la serie (1^3 + 2^3 + 3^3 + … + n^3) mod 4 para un n dado

Dada una función f(n) = (1 ³ + 2 ³ + 3 ³ + … + n ³ ), la tarea es encontrar el valor de f(n) mod 4 para un entero positivo dado ‘n’. 
Ejemplos 
 

Input: n=6
Output: 1
Explanation: f(6) = 1+8+27+64+125+216=441
f(n) mod 4=441 mod 4 = 1

Input: n=4
Output: 0
Explanation: f(4)=1+8+27+64 = 100
f(n) mod 4 =100 mod 4 = 0

Al resolver este problema, puede calcular directamente (1 ³ + 2 ³ + 3 ³ + … + n ³ ) mod 4. Pero esto requiere tiempo O(n). Podemos usar la fórmula directa para la suma de cubos , pero para ‘n’ grande podemos obtener f(n) fuera del rango de long long int.
Aquí hay una solución O(1) eficiente:
del algoritmo de división sabemos que cada número entero se puede expresar como 4k, 4k+1, 4k+2 o 4k+3. 
Ahora,
 

(4k) ³ = 64k ³ módulo 4 = 0. 
(4k+1) ³ = (64k ³ + 48k ² + 12k+1) módulo 4 = 1 
(4k+2) ³ = (64k ³ +64k ² +48k+ 8) módulo 4 = 0 
(4k+3) ³ = (64k ³ +184k ² + 108k+27) módulo 4 = 3 
y ((4k) ³ +(4k+1) ³ +(4k+2) ³ +( 4k+1) ⁴ ) módulo 4 = (0 + 1+ 0 + 3) módulo 4 = 0 módulo 4 
 

Ahora sea x el entero más grande no mayor que n divisible por 4. Entonces podemos ver fácilmente que, 
(1 ³ +2 ³ +3 ³ …..+x ³ ) mod 4=0. 
Ahora, 
 

• si n es un divisor de 4 entonces x=n y f(n) mod 4 =0.
• De lo contrario, si n tiene la forma 4k + 1, entonces x= n-1. Entonces, f(n)= 1 ³ + 2 ³ + 3 ³ …..+ x ³ +n ³ ) módulo 4 = n^3 módulo 4 = 1
• De manera similar, si n tiene la forma 4k+2 (es decir, x=n-2), podemos demostrar fácilmente que f(n) = ((n-1) ³ +n ³ ) mod 4=(1 + 0) mod 4 = 1
• Y si n es de la forma 4k+3 (x=n-3). De manera similar, obtenemos f(n) mod 4 = ((n-2) ³ +(n-1) ³ +n ³ ) mod 4 = (1+0+3) mod 4 = 0

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

// C++ implementation of the approach
#include <iostream>
using namespace std;
 
// function for obtaining the value of f(n) mod 4
int fnMod(int n)
{
    // Find the remainder of n when divided by 4
    int rem = n % 4;
 
    // If n is of the form 4k or 4k+3
    if (rem == 0 || rem == 3)
        return 0;
 
    // If n is of the form 4k+1 or 4k+2
    else if (rem == 1 || rem == 2)
        return 1;
}
 
// Driver code
int main()
{
    int n = 6;
    cout << fnMod(n);
    return 0;
}

// Java implementation of the approach
 
import java .io.*;
 
class GFG {
  
// function for obtaining the value of f(n) mod 4
static int fnMod(int n)
{
    // Find the remainder of n when divided by 4
    int rem = n % 4;
 
    // If n is of the form 4k or 4k+3
    if (rem == 0 || rem == 3)
        return 0;
 
    // If n is of the form 4k+1 or 4k+2
    else if (rem == 1 || rem == 2)
        return 1;
        return 0;
}
 
// Driver code
 
    public static void main (String[] args) {
            int n = 6;
    System.out.print( fnMod(n));
    }
}
//This code is contributed
// by shs

# Python3 implementation of
# above approach
 
# function for obtaining the
# value of f(n) mod 4
def fnMod(n) :
 
    # Find the remainder of n
    # when divided by 4
    rem = n % 4
 
    # If n is of the form 4k or 4k+3
    if (rem == 0 or rem == 3) :
        return 0
 
    # If n is of the form
    # 4k+1 or 4k+2
    elif (rem == 1 or rem == 2) :
        return 1
 
# Driver code    
if __name__ == "__main__" :
 
    n = 6
    print(fnMod(n))
 
# This code is contributed
# by ANKITRAI1

// C# implementation of the approach
  
 
using System;
class GFG {
   
// function for obtaining the value of f(n) mod 4
static int fnMod(int n)
{
    // Find the remainder of n when divided by 4
    int rem = n % 4;
  
    // If n is of the form 4k or 4k+3
    if (rem == 0 || rem == 3)
        return 0;
  
    // If n is of the form 4k+1 or 4k+2
    else if (rem == 1 || rem == 2)
        return 1;
        return 0;
}
  
// Driver code
  
    public static void Main () {
            int n = 6;
    Console.Write( fnMod(n));
    }
}

<?php
// PHP implementation of the approach
 
// function for obtaining the
// value of f(n) mod 4
function fnMod($n)
{
    // Find the remainder of n
    // when divided by 4
    $rem = $n % 4;
 
    // If n is of the form 4k or 4k+3
    if ($rem == 0 or $rem == 3)
        return 0;
 
    // If n is of the form 4k+1 or 4k+2
    else if ($rem == 1 or $rem == 2)
        return 1;
}
 
// Driver code
$n = 6;
echo fnMod($n);
 
// This code is contributed
// by anuj_67..
?>

<script>
 
// Javascript implementation of the approach
 
// Function for obtaining the value
// of f(n) mod 4
function fnMod(n)
{
     
    // Find the remainder of n
    // when divided by 4
    var rem = n % 4;
     
    // If n is of the form 4k or 4k+3
    if (rem == 0 || rem == 3)
        return 0;
 
    // If n is of the form 4k+1 or 4k+2
    else if (rem == 1 || rem == 2)
        return 1;
         
    return 0;
}
 
// Driver Code
var n = 6;
 
document.write(fnMod(n));
 
// This code is contributed by Kirti
 
</script>

1