Encuentra (1^n + 2^n + 3^n + 4^n) módulo 5 | conjunto 2

Dado un número muy grande N . La tarea es encontrar (1 ⁿ + 2 ⁿ + 3 ⁿ + 4 ⁿ ) mod 5 .
Ejemplos: 
 

Entrada: N = 4 
Salida: 4 
(1 + 16 + 81 + 256) % 5 = 354 % 5 = 4
Entrada: N = 7823462937826332873467731 
Salida: 0 
 

Enfoque: (1 ⁿ + 2 ⁿ + 3 ⁿ + 4 ⁿ ) mod 5 = (1 ^{n mod ?(5)} + 2 ^{n mod ?(5)} + 3 ^{n mod ?(5)} + 4 ^{n mod ?(5)} ) mod 5. 
Esta fórmula es correcta porque 5 es un número primo y es coprimo con 1, 2, 3, 4. 
Conoce sobre ?(n) y el módulo de un número grande  
?(5) = 4 , por lo tanto (1 ⁿ + 2 ^norte + 3 ^norte + 4 ^norte ) mod 5 = (1 ^{norte mod 4} + 2 ^{norte mod 4} + 3 ^{norte mod 4} + 4 ^{norte mod 4}) mod 5
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return A mod B
int A_mod_B(string N, int a)
{
    // length of the string
    int len = N.size();
 
    // to store required answer
    int ans = 0;
    for (int i = 0; i < len; i++)
        ans = (ans * 10 + (int)N[i] - '0') % a;
 
    return ans % a;
}
 
// Function to return (1^n + 2^n + 3^n + 4^n) % 5
int findMod(string N)
{
    // ?(5) = 4
    int mod = A_mod_B(N, 4);
 
    int ans = (1 + pow(2, mod) + pow(3, mod)
               + pow(4, mod));
 
    return (ans % 5);
}
 
// Driver code
int main()
{
    string N = "4";
    cout << findMod(N);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
// Function to return A mod B
static int A_mod_B(String N, int a)
{
    // length of the string
    int len = N.length();
 
    // to store required answer
    int ans = 0;
    for (int i = 0; i < len; i++)
        ans = (ans * 10 + (int)N.charAt(i) - '0') % a;
 
    return ans % a;
}
 
// Function to return (1^n + 2^n + 3^n + 4^n) % 5
static int findMod(String N)
{
    // ?(5) = 4
    int mod = A_mod_B(N, 4);
 
    int ans = (1 + (int)Math.pow(2, mod) +
                (int)Math.pow(3, mod) +
                (int)Math.pow(4, mod));
 
    return (ans % 5);
}
 
// Driver code
public static void main(String args[])
{
    String N = "4";
    System.out.println(findMod(N));
}
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation of the approach
 
# Function to return A mod B
def A_mod_B(N, a):
     
    # length of the string
    Len = len(N)
 
    # to store required answer
    ans = 0
    for i in range(Len):
        ans = (ans * 10 + int(N[i])) % a
 
    return ans % a
 
# Function to return (1^n + 2^n + 3^n + 4^n) % 5
def findMod(N):
 
    # ?(5) = 4
    mod = A_mod_B(N, 4)
 
    ans = (1 + pow(2, mod) +
               pow(3, mod) + pow(4, mod))
 
    return ans % 5
 
# Driver code
N = "4"
print(findMod(N))
 
# This code is contributed by mohit kumar

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return A mod B
static int A_mod_B(string N, int a)
{
    // length of the string
    int len = N.Length;
 
    // to store required answer
    int ans = 0;
    for (int i = 0; i < len; i++)
        ans = (ans * 10 + (int)N[i] - '0') % a;
 
    return ans % a;
}
 
// Function to return (1^n + 2^n + 3^n + 4^n) % 5
static int findMod(string N)
{
    // ?(5) = 4
    int mod = A_mod_B(N, 4);
 
    int ans = (1 + (int)Math.Pow(2, mod) +
                (int)Math.Pow(3, mod) +
                (int)Math.Pow(4, mod));
 
    return (ans % 5);
}
 
// Driver code
public static void Main()
{
    string N = "4";
    Console.WriteLine(findMod(N));
}
}
 
// This code is contributed by Code_Mech.

<?php
// PHP implementation of the approach
 
// Function to return A mod B
function A_mod_B($N, $a)
{
    // length of the string
    $len = strlen($N);
 
    // to store required answer
    $ans = 0;
    for ($i = 0; $i < $len; $i++)
        $ans = ($ans * 10 +
               (int)$N[$i] - '0') % $a;
 
    return $ans % $a;
}
 
// Function to return
// (1^n + 2^n + 3^n + 4^n) % 5
function findMod($N)
{
    // ?(5) = 4
    $mod = A_mod_B($N, 4);
 
    $ans = (1 + pow(2, $mod) +
                pow(3, $mod) + pow(4, $mod));
 
    return ($ans % 5);
}
 
// Driver code
$N = "4";
echo findMod($N);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
 
// Javascript implementation of the approach
 
// Function to return A mod B
function A_mod_B(N, a)
{
    // length of the string
    var len = N.length;
 
    // to store required answer
    var ans = 0;
    for (var i = 0; i < len; i++)
        ans = (ans * 10 + parseInt(N.charAt(i) - '0')) % a;
 
    return ans % a;
}
 
// Function to return (1^n + 2^n + 3^n + 4^n) % 5
function findMod(N)
{
    // ?(5) = 4
    var mod = A_mod_B(N, 4);
 
    var ans = (1 + parseInt(Math.pow(2, mod) +
                Math.pow(3, mod) +
                Math.pow(4, mod)));
 
    return (ans % 5);
}
 
// Driver Code
var N = "4";
     
// Function call
document.write(findMod(N));
 
// This code is contributed by Kirti
 
</script>

4

Complejidad de tiempo: O(|N|), donde |N| es la longitud de la string.
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.