Suma de todos los números naturales de L a R (para valores grandes de L y R)

Dados dos números muy grandes L y R donde L ≤ R , la tarea es calcular la suma de todos los números naturales de L a R . La suma podría ser grande, así que imprima la suma % 1000000007 .
Ejemplos:

Entrada: L = “8894” R = “98592”
Salida: 820693329
Entrada: L = “88949273204” R = “98429729474298592”
Salida: 252666158

Acercarse:

Let sum(N) es una función que devuelve la suma de los primeros N números naturales.
La suma de los primeros N números naturales es sum(N) = (N * (N + 1)) / 2 .
La suma de los números en el rango entre L y R será RangeSum = sum(R) – sum(L – 1)
La respuesta se calcula con el módulo 10 ⁹ + 7 , Entonces,

mod = 10 ⁹ + 7
RangeSum = (sum(R) – sum(L-1) + mod)%mod;
Esto también se puede escribir como RangeSum = (sum(R)%mod – sum(L-1)%mod + mod)%mod;
Ahora, sum(R) % mod se puede escribir como ((R * (R + 1)) / 2) % mod
O ((R % mod) * ((R + 1) % mod) * invmod(2)) % mod
Dado que R es grande, el módulo de R se puede calcular como se describe aquí .
El valor de inversemod(2) = 500000004 que se puede calcular usando el pequeño teorema de Fermat .
De manera similar, también se puede calcular sum(L – 1) % mod .

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define mod 1000000007
 
// Value of inverse modulo
// 2 with 10^9 + 7
const long long inv2 = 500000004;
 
// Function to return num % 1000000007
// where num is a large number
long long int modulo(string num)
{
    // Initialize result
    long long int res = 0;
 
    // One by one process all the
    // digits of string 'num'
    for (long long int i = 0;
         i < num.length();
         i++)
        res = (res * 10
               + (long long int)num[i]
               - '0')
              % mod;
    return res;
}
 
// Function to return the sum of the
// integers from the given range
// modulo 1000000007
long long int findSum(string L,
                      string R)
{
    long long int a, b, l, r, ret;
 
    // a stores the value of
    // L modulo 10^9 + 7
    a = modulo(L);
 
    // b stores the value of
    // R modulo 10^9 + 7
    b = modulo(R);
 
    // l stores the sum of natural
    // numbers from 1 to (a - 1)
    l = ((a * (a - 1))
         % mod * inv2)
        % mod;
 
    // r stores the sum of natural
    // numbers from 1 to b
    r = ((b * (b + 1))
         % mod * inv2)
        % mod;
 
    ret = (r % mod - l % mod);
 
    // If the result is negative
    if (ret < 0)
        ret = ret + mod;
    else
        ret = ret % mod;
    return ret;
}
 
// Driver code
int main()
{
    string L = "88949273204";
    string R = "98429729474298592";
 
    cout << findSum(L, R) << endl;
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
static long mod = 1000000007;
 
// Value of inverse modulo
// 2 with 10^9 + 7
static long inv2 = 500000004;
 
// Function to return num % 1000000007
// where num is a large number
static long modulo(String num)
{
    // Initialize result
    long res = 0;
 
    // One by one process all the
    // digits of string 'num'
    for (int i = 0;
             i < num.length(); i++)
        res = (res * 10 +
              (long)num.charAt(i) - '0') % mod;
    return res;
}
 
// Function to return the sum of the
// longegers from the given range
// modulo 1000000007
static long findSum(String L, String R)
{
    long a, b, l, r, ret;
 
    // a stores the value of
    // L modulo 10^9 + 7
    a = modulo(L);
 
    // b stores the value of
    // R modulo 10^9 + 7
    b = modulo(R);
 
    // l stores the sum of natural
    // numbers from 1 to (a - 1)
    l = ((a * (a - 1)) % mod * inv2) % mod;
 
    // r stores the sum of natural
    // numbers from 1 to b
    r = ((b * (b + 1)) % mod * inv2) % mod;
 
    ret = (r % mod - l % mod);
 
    // If the result is negative
    if (ret < 0)
        ret = ret + mod;
    else
        ret = ret % mod;
    return ret;
}
 
// Driver code
public static void main(String[] args)
{
    String L = "88949273204";
    String R = "98429729474298592";
 
    System.out.println(findSum(L, R));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of the approach
mod = 1000000007
 
# Value of inverse modulo
# 2 with 10^9 + 7
inv2 = 500000004;
 
# Function to return num % 1000000007
# where num is a large number
def modulo(num) :
 
    # Initialize result
    res = 0;
 
    # One by one process all the
    # digits of string 'num'
    for i in range(len(num)) :
        res = (res * 10 + int(num[i]) - 0) % mod;
         
    return res;
 
# Function to return the sum of the
# integers from the given range
# modulo 1000000007
def findSum(L, R) :
     
    # a stores the value of
    # L modulo 10^9 + 7
    a = modulo(L);
 
    # b stores the value of
    # R modulo 10^9 + 7
    b = modulo(R);
 
    # l stores the sum of natural
    # numbers from 1 to (a - 1)
    l = ((a * (a - 1)) % mod * inv2) % mod;
 
    # r stores the sum of natural
    # numbers from 1 to b
    r = ((b * (b + 1)) % mod * inv2) % mod;
 
    ret = (r % mod - l % mod);
 
    # If the result is negative
    if (ret < 0) :
        ret = ret + mod;
    else :
        ret = ret % mod;
         
    return ret;
 
# Driver code
if __name__ == "__main__" :
 
    L = "88949273204";
    R = "98429729474298592";
 
    print(findSum(L, R)) ;
     
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
     
class GFG
{
static long mod = 1000000007;
 
// Value of inverse modulo
// 2 with 10^9 + 7
static long inv2 = 500000004;
 
// Function to return num % 1000000007
// where num is a large number
static long modulo(String num)
{
    // Initialize result
    long res = 0;
 
    // One by one process all the
    // digits of string 'num'
    for (int i = 0;
             i < num.Length; i++)
        res = (res * 10 +
              (long)num[i] - '0') % mod;
    return res;
}
 
// Function to return the sum of the
// longegers from the given range
// modulo 1000000007
static long findSum(String L, String R)
{
    long a, b, l, r, ret;
 
    // a stores the value of
    // L modulo 10^9 + 7
    a = modulo(L);
 
    // b stores the value of
    // R modulo 10^9 + 7
    b = modulo(R);
 
    // l stores the sum of natural
    // numbers from 1 to (a - 1)
    l = ((a * (a - 1)) % mod * inv2) % mod;
 
    // r stores the sum of natural
    // numbers from 1 to b
    r = ((b * (b + 1)) % mod * inv2) % mod;
 
    ret = (r % mod - l % mod);
 
    // If the result is negative
    if (ret < 0)
        ret = ret + mod;
    else
        ret = ret % mod;
    return ret;
}
 
// Driver code
public static void Main(String[] args)
{
    String L = "88949273204";
    String R = "98429729474298592";
 
    Console.WriteLine(findSum(L, R));
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
    // Javascript implementation of the approach
     
    let mod = 1000000007;
   
    // Value of inverse modulo
    // 2 with 10^9 + 7
    let inv2 = 500000004;
 
    // Function to return num % 1000000007
    // where num is a large number
    function modulo(num)
    {
        // Initialize result
        let res = 0;
 
        // One by one process all the
        // digits of string 'num'
        for (let i = 0;
                 i < num.length; i++)
            res = (res * 10 + num[i].charCodeAt() - '0'.charCodeAt()) % mod;
        return res;
    }
 
    // Function to return the sum of the
    // longegers from the given range
    // modulo 1000000007
    function findSum(L, R)
    {
        let a, b, l, r, ret;
 
        // a stores the value of
        // L modulo 10^9 + 7
        a = modulo(L);
 
        // b stores the value of
        // R modulo 10^9 + 7
        b = modulo(R);
 
        // l stores the sum of natural
        // numbers from 1 to (a - 1)
        l = ((a * (a - 1)) % mod * inv2) % mod;
 
        // r stores the sum of natural
        // numbers from 1 to b
        r = ((b * (b + 1)) % mod * inv2) % mod;
 
        ret = (r % mod - l % mod);
 
        // If the result is negative
        if (ret < 0)
            ret = ret + mod;
        else
            ret = ret % mod - 6;
        return ret;
    }
     
    let L = "88949273204";
    let R = "98429729474298592";
   
    document.write(findSum(L, R));
 
// This code is contributed by decode2207.
</script>

Producción:

252666158

Complejidad de tiempo: O(|L| + |R|)

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por Pratims10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta