Dados tres enteros A , B y C , la tarea es encontrar el valor de la expresión
Dado que la respuesta puede ser muy grande, imprima la respuesta módulo 10 9 + 7 .
Ejemplos:
Entrada: A = 1, B = 1, C = 2
Salida: 3
Explicación: El valor de la expresión dada es: (1 * 1 * 1 + 1 * 1 * 2) % (10 9 + 7) = 3
Por lo tanto, la salida requerida es 3.Entrada: A = 10, B = 100, C = 1000
Salida: 13874027
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los tripletes posibles (i, j, k) e imprimir la suma de todos los productos posibles (i * j * k) mod (10 9 + 7) .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; #define M 1000000007 // Function to find the sum of all // possible triplet products (i * j * k) long long findTripleSum(long long A, long long B, long long C) { // Stores sum required sum long long sum = 0; // Iterate over all // possible values of i for (long long i = 1; i <= A; i++) { // Iterate over all // possible values of j for (long long j = 1; j <= B; j++) { // Iterate over all // possible values of k for (long long k = 1; k <= C; k++) { // Stores the product // of (i * j *k) long long prod = (((i % M) * (j % M)) % M * (k % M)) % M; // Update sum sum = (sum + prod) % M; } } } return sum; } // Driver Code int main() { long long A = 10; long long B = 100; long long C = 1000; cout << findTripleSum(A, B, C); return 0; }
Java
// Java program to implement // the above approach import java.util.*; class GFG{ static int M = 1000000007; // Function to find the sum of all // possible triplet products (i * j * k) static int findTripleSum(int A, int B, int C) { // Stores sum required sum int sum = 0; // Iterate over all // possible values of i for(int i = 1; i <= A; i++) { // Iterate over all // possible values of j for(int j = 1; j <= B; j++) { // Iterate over all // possible values of k for(int k = 1; k <= C; k++) { // Stores the product // of (i * j *k) int prod = (((i % M) * (j % M)) % M * (k % M)) % M; // Update sum sum = (sum + prod) % M; } } } return sum; } // Driver Code public static void main(String args[]) { int A = 10; int B = 100; int C = 1000; System.out.println(findTripleSum(A, B, C)); } } // This code is contributed by bgangwar59
Python3
# Python3 program to implement # the above approach M = 1000000007 # Function to find the sum # of all possible triplet # products (i * j * k) def findTripleSum(A, B, C): # Stores sum required sum sum = 0 # Iterate over all # possible values of i for i in range(1, A + 1): # Iterate over all # possible values of j for j in range(1, B + 1): # Iterate over all # possible values of k for k in range(1, C + 1): # Stores the product # of (i * j *k) prod = (((i % M) * (j % M)) % M * (k % M)) % M # Update sum sum = (sum + prod) % M return sum # Driver Code if __name__ == '__main__': A = 10 B = 100 C = 1000 print(findTripleSum(A, B, C)) # This code is contributed by mohit kumar 29
C#
// C# program to implement // the above approach using System; class GFG{ static int M = 1000000007; // Function to find the sum of all // possible triplet products (i * j * k) static int findTripleSum(int A, int B, int C) { // Stores sum required sum int sum = 0; // Iterate over all // possible values of i for(int i = 1; i <= A; i++) { // Iterate over all // possible values of j for(int j = 1; j <= B; j++) { // Iterate over all // possible values of k for(int k = 1; k <= C; k++) { // Stores the product // of (i * j *k) int prod = (((i % M) * (j % M)) % M * (k % M)) % M; // Update sum sum = (sum + prod) % M; } } } return sum; } // Driver Code public static void Main() { int A = 10; int B = 100; int C = 1000; Console.WriteLine(findTripleSum(A, B, C)); } } // This code is contributed by code_hunt
Javascript
<script> // JavaScript program to implement the above approach let M = 1000000007; // Function to find the sum of all // possible triplet products (i * j * k) function findTripleSum(A, B, C) { // Stores sum required sum let sum = 0; // Iterate over all // possible values of i for(let i = 1; i <= A; i++) { // Iterate over all // possible values of j for(let j = 1; j <= B; j++) { // Iterate over all // possible values of k for(let k = 1; k <= C; k++) { // Stores the product // of (i * j *k) let prod = (((i % M) * (j % M)) % M * (k % M)) % M; // Update sum sum = (sum + prod) % M; } } } return sum; } // Driver Code let A = 10; let B = 100; let C = 1000; document.write(findTripleSum(A, B, C)); // This code is contributed by susmitakunndugoaldanga. </script>
13874027
Complejidad de Tiempo: O(A * B * C)
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
Suma simple:
Doble suma:
= ((A * (A + 1) / 2) * (B * (B + 1) / 2))
Del mismo modo, para la suma triple:
= ((A * (A + 1) / 2) * (B * (B + 1) / 2) * (C * (C+ 1) / 2))
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos MMI para almacenar el módulo inverso multiplicativo de 8 .
- Inicialice una variable, digamos M , para almacenar el valor de 10 9 + 7 .
Finalmente, imprima el valor de ((A * (A + 1) % M) * (B * (B + 1) % M) * (C * (C+ 1) % M) * MMI) % M .
C++
// C++ implementation to implement // the above approach #include <bits/stdc++.h> using namespace std; #define M 1000000007 // Function to find the value // of power(X, N) % M long long power(long long x, long long N) { // Stores the value // of (X ^ N) % M long long res = 1; // Calculate the value of // power(x, N) % M while (N > 0) { // If N is odd if (N & 1) { // Update res res = (res * x) % M; } // Update x x = (x * x) % M; // Update N N = N >> 1; } return res; } // Function to find modulo multiplicative // inverse of X under modulo M long long modinv(long long X) { return power(X, M - 2); } // Function to find the sum of all // possible triplet products (i * j * k) int findTripleSum(long long A, long long B, long long C) { // Stores modulo multiplicative // inverse of 8 long long MMI = modinv(8); // Stores the sum of all // possible values of (i * j * k) long long res = 0; // Update res res = ((((A % M * (A + 1) % M) % M * (B % M * (B + 1) % M) % M) % M * (C % M * (C + 1) % M) % M) % M * MMI) % M; return res; } // Driver Code int main() { long long A = 10; long long B = 100; long long C = 1000; cout << findTripleSum(A, B, C); return 0; }
Java
// Java implementation to implement // the above approach import java.util.*; class GFG{ static final int M = 1000000007; // Function to find the value // of power(X, N) % M static long power(long x, long N) { // Stores the value // of (X ^ N) % M long res = 1; // Calculate the value of // power(x, N) % M while (N > 0) { // If N is odd if (N % 2 == 1) { // Update res res = (res * x) % M; } // Update x x = (x * x) % M; // Update N N = N >> 1; } return res; } // Function to find modulo multiplicative // inverse of X under modulo M static long modinv(long X) { return power(X, M - 2); } // Function to find the sum of all // possible triplet products (i * j * k) static long findTripleSum(long A, long B, long C) { // Stores modulo multiplicative // inverse of 8 long MMI = modinv(8); // Stores the sum of all // possible values of (i * j * k) long res = 0; // Update res res = ((((A % M * (A + 1) % M) % M * (B % M * (B + 1) % M) % M) % M * (C % M * (C + 1) % M) % M) % M * MMI) % M; return res; } // Driver Code public static void main(String[] args) { long A = 10; long B = 100; long C = 1000; System.out.print(findTripleSum(A, B, C)); } } // This code is contributed by Rajput-Ji
Python3
# Python3 implementation to # implement the above approach M = 1000000007 # Function to find the value # of power(X, N) % M def power(x,N): global M # Stores the value # of (X ^ N) % M res = 1 # Calculate the value of # power(x, N) % M while (N > 0): # If N is odd if (N & 1): # Update res res = (res * x) % M # Update x x = (x * x) % M # Update N N = N >> 1 return res # Function to find modulo # multiplicative inverse # of X under modulo M def modinv(X): return power(X, M - 2) # Function to find the # sum of all possible # triplet products (i * j * k) def findTripleSum(A, B, C): global M # Stores modulo multiplicative # inverse of 8 MMI = modinv(8) # Stores the sum of all # possible values of (i * j * k) res = 0 # Update res res = ((((A % M * (A + 1) % M) % M * (B % M * (B + 1) % M) % M) % M * (C % M * (C + 1) % M) % M) % M * MMI)% M return res # Driver Code if __name__ == '__main__': A = 10 B = 100 C = 1000 print(findTripleSum(A, B, C)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# implementation to implement // the above approach using System; class GFG{ static readonly int M = 1000000007; // Function to find the value // of power(X, N) % M static long power(long x, long N) { // Stores the value // of (X ^ N) % M long res = 1; // Calculate the value of // power(x, N) % M while (N > 0) { // If N is odd if (N % 2 == 1) { // Update res res = (res * x) % M; } // Update x x = (x * x) % M; // Update N N = N >> 1; } return res; } // Function to find modulo multiplicative // inverse of X under modulo M static long modinv(long X) { return power(X, M - 2); } // Function to find the sum of all // possible triplet products (i * j * k) static long findTripleSum(long A, long B, long C) { // Stores modulo multiplicative // inverse of 8 long MMI = modinv(8); // Stores the sum of all // possible values of (i * j * k) long res = 0; // Update res res = ((((A % M * (A + 1) % M) % M * (B % M * (B + 1) % M) % M) % M * (C % M * (C + 1) % M) % M) % M * MMI) % M; return res; } // Driver Code public static void Main(String[] args) { long A = 10; long B = 100; long C = 1000; Console.Write(findTripleSum(A, B, C)); } } // This code is contributed by Amit Katiyar
13874027
Complejidad de Tiempo: O(log 2 N), Donde N = (A * B * C)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por subhash1raja y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA