Suma de múltiplos de A y B menores que N

Dado un número N, la tarea es encontrar la suma de todos los múltiplos de A y B debajo de N.
Ejemplos: 
 

Input:N = 11, A= 8, B= 2
Output: Sum = 30
Multiples of 8 less than 11 is 8 only.
Multiples of 2 less than 11 is 2, 4, 6, 8, 10 and their sum is 30.
As 8 is common in both so it is counted only once.

Input: N = 100, A= 5, B= 10
Output: Sum = 950

Un enfoque ingenuo es iterar a través de 1 y encontrar los múltiplos de A y B y sumarlos a la suma. Al final del ciclo, muestra la suma.
Enfoque eficiente: Como los múltiplos de A formarán una serie AP a, 2a, 3a…. 
y B forma una serie AP b, 2b, 3b… 
Al sumar la suma de estas dos series obtendremos la suma de los múltiplos de ambos números, pero puede haber algunos múltiplos comunes, así que elimine los duplicados de la suma de estas dos series por restando los múltiplos de mcm(A, B). Entonces, resta la serie de mcm(A, B) . 
Entonces, la suma de los múltiplos de A y B menores que N es Sum(A)+Sum(B)-Sum(lcm(A, B)) .
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to find the sum of all
// multiples of A and B below N
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
// Function to find sum of AP series
ll sumAP(ll n, ll d)
{
    // Number of terms
    n /= d;
 
    return (n) * (1 + n) * d / 2;
}
 
// Function to find the sum of all
// multiples of A and B below N
ll sumMultiples(ll A, ll B, ll n)
{
    // Since, we need the sum of
    // multiples less than N
    n--;
 
    // common factors of A and B
    ll common = (A * B) / __gcd(A, B);
 
    return sumAP(n, A) + sumAP(n, B) - sumAP(n, common);
}
 
// Driver code
int main()
{
    ll n = 100, A = 5, B = 10;
 
    cout << "Sum = " << sumMultiples(A, B, n);
 
    return 0;
}

// Java program to find the sum of all
// multiples of A and B below N
 
class GFG{
 
static int __gcd(int a, int b)
    {
      if (b == 0)
        return a;
      return __gcd(b, a % b); 
    }
     
// Function to find sum of AP series
static int sumAP(int n, int d)
{
    // Number of terms
    n /= d;
 
    return (n) * (1 + n) * d / 2;
}
 
// Function to find the sum of all
// multiples of A and B below N
static int sumMultiples(int A, int B, int n)
{
    // Since, we need the sum of
    // multiples less than N
    n--;
 
    // common factors of A and B
    int common = (A * B) / __gcd(A,B);
 
    return sumAP(n, A) + sumAP(n, B) - sumAP(n, common);
}
 
// Driver code
public static void main(String[] args)
{
    int n = 100, A = 5, B = 10;
 
    System.out.println("Sum = "+sumMultiples(A, B, n));
}
}
// this code is contributed by mits

# Python 3 program to find the sum of
# all multiples of A and B below N
from math import gcd,sqrt
 
# Function to find sum of AP series
def sumAP(n, d):
     
    # Number of terms
    n = int(n / d)
 
    return (n) * (1 + n) * d / 2
 
# Function to find the sum of all
# multiples of A and B below N
def sumMultiples(A, B, n):
     
    # Since, we need the sum of
    # multiples less than N
    n -= 1
 
    # common factors of A and B
    common = int((A * B) / gcd(A, B))
 
    return (sumAP(n, A) + sumAP(n, B) -
            sumAP(n, common))
 
# Driver code
if __name__ == '__main__':
    n = 100
    A = 5
    B = 10
 
    print("Sum =", int(sumMultiples(A, B, n)))
 
# This code is contributed by
# Surendra_Gangwar

// C# program to find the sum of all
// multiples of A and B below N
 
class GFG{
 
static int __gcd(int a, int b)
    {
    if (b == 0)
        return a;
    return __gcd(b, a % b);
    }
     
// Function to find sum of AP series
static int sumAP(int n, int d)
{
    // Number of terms
    n /= d;
 
    return (n) * (1 + n) * d / 2;
}
 
// Function to find the sum of all
// multiples of A and B below N
static int sumMultiples(int A, int B, int n)
{
    // Since, we need the sum of
    // multiples less than N
    n--;
 
    // common factors of A and B
    int common = (A * B) / __gcd(A,B);
 
    return sumAP(n, A) + sumAP(n, B) - sumAP(n, common);
}
 
// Driver code
public static void Main()
{
    int n = 100, A = 5, B = 10;
 
    System.Console.WriteLine("Sum = "+sumMultiples(A, B, n));
}
}
// this code is contributed by mits

<?php
// PHP program to find the sum of all
// multiples of A and B below N
function __gcd($a,$b)
{
    if ($b == 0)
        return $a;
    return __gcd($b, $a % $b);
}
 
// Function to find sum of AP series
function sumAP($n, $d)
{
    // Number of terms
    $n = (int)($n / $d);
 
    return ($n) * (1 + $n) * $d / 2;
}
 
// Function to find the sum of all
// multiples of A and B below N
function sumMultiples($A, $B, $n)
{
    // Since, we need the sum of
    // multiples less than N
    $n--;
 
    // common factors of A and B
    $common = (int)(($A * $B) /
               __gcd($A, $B));
 
    return sumAP($n, $A) +
           sumAP($n, $B) -
           sumAP($n, $common);
}
 
// Driver code
$n = 100;
$A = 5;
$B = 10;
 
echo "Sum = " . sumMultiples($A, $B, $n);
 
// This code is contributed by mits
?>

<script>
 
// JavaScript  program to find the sum of all
// multiples of A and B below N
function __gcd(a,b)
{
    if (b == 0)
        return a;
    return __gcd(b, a % b);
}
 
// Function to find sum of AP series
function sumAP(n, d)
{
    // Number of terms
    n = parseInt(n / d);
 
    return (n) * (1 + n) * d / 2;
}
 
// Function to find the sum of all
// multiples of A and B below N
function sumMultiples(A, B, n)
{
    // Since, we need the sum of
    // multiples less than N
    n--;
 
    // common factors of A and B
    common = parseInt((A * B) /
               __gcd(A, B));
 
    return sumAP(n, A) +
           sumAP(n, B) -
           sumAP(n, common);
}
 
// Driver code
let n = 100;
let A = 5;
let B = 10;
 
document.write( "Sum = " + sumMultiples(A, B, n));
 
 
// This code is contributed by bobby
 
</script>

Sum = 950

Complejidad de tiempo: O(log(min(a, b))), donde a y b son dos parámetros de gcd.

Espacio auxiliar: O(log(min(a, b)))