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>
Producción:
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
Producción:
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