Dado un número muy grande N . La tarea es encontrar (1 n + 2 n + 3 n + 4 n ) mod 5 .
Ejemplos:
Entrada: N = 4
Salida: 4
(1 + 16 + 81 + 256) % 5 = 354 % 5 = 4
Entrada: N = 7823462937826332873467731
Salida: 0
Enfoque: (1 n + 2 n + 3 n + 4 n ) 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 n + 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++
// 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
// 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
# 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#
// 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 // 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 ?>
Javascript
<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.
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA