Suma de los primeros N números naturales que son divisibles por X o Y

Dado un número N. Dados dos números X e Y , la tarea es encontrar la suma de todos aquellos números del 1 al N que son divisibles por X o por Y.
Ejemplos : 
 

Input : N = 20
Output : 98

Input : N = 14 
Output : 45

Enfoque : para resolver el problema, siga los pasos a continuación:
->Encuentre la suma de los números que son divisibles por X hasta N. Denótela como S1. 
->Encuentra la suma de los números que son divisibles por Y hasta N. Denota por S2. 
->Encuentra la suma de los números que son divisibles tanto por X como por Y (X*Y) hasta N. Denota por S3. 
->La respuesta final será S1 + S2 – S3 .
Para encontrar la suma, podemos usar la fórmula general de AP que es: 
 

Sn = (n/2) * {2*a + (n-1)*d}

Para S1 : Los números totales que serán divisibles por X hasta N serán N/X y la suma será: 
 

Hence, 
S1 = ((N/X)/2) * (2 * X + (N/X - 1) * X)

Para S2 : Los números totales que serán divisibles por Y hasta N serán N/Y y la suma será: 
 

Hence, 
S2 = ((N/Y)/2) * (2 * Y + (N/Y - 1) * Y)

Para S3 : los números totales que serán divisibles tanto por X como por Y hasta N serán N/(X*Y) y la suma será: 
 

Hence, 
S2 = ((N/(X*Y))/2) * (2 * Y + (N/(X*Y) - 1) * (X*Y))

Por tanto, el resultado será: 
 

S = S1 + S2 - S3

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

// C++ program to find sum of numbers from
// 1 to N which are divisible by X or Y
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the sum
// of numbers divisible by X or Y
int sum(int N, int X, int Y)
{
    int S1, S2, S3;
 
    S1 = ((N / X)) * (2 * X + (N / X - 1) * X) / 2;
    S2 = ((N / Y)) * (2 * Y + (N / Y - 1) * Y) / 2;
    S3 = ((N / (X * Y))) * (2 * (X * Y)
                      + (N / (X * Y) - 1) * (X * Y))/ 2;
 
    return S1 + S2 - S3;
}
 
// Driver code
int main()
{
    int N = 14;
    int X = 3, Y = 5;
 
    cout << sum(N, X, Y);
 
    return 0;
}

// Java program to find sum of numbers from
// 1 to N which are divisible by X or Y
 
public class GFG{
     
    // Function to calculate the sum
    // of numbers divisible by X or Y
    static int sum(int N, int X, int Y)
    {
        int S1, S2, S3;
     
        S1 = ((N / X)) * (2 * X + (N / X - 1) * X) / 2;
        S2 = ((N / Y)) * (2 * Y + (N / Y - 1) * Y) / 2;
        S3 = ((N / (X * Y))) * (2 * (X * Y)
                          + (N / (X * Y) - 1) * (X * Y))/ 2;
     
        return S1 + S2 - S3;
    }
     
    // Driver code
    public static void main(String []args)
    {
        int N = 14;
        int X = 3, Y = 5;
     
        System.out.println(sum(N, X, Y));
     
    }
    // This code is contributed by Ryuga
}

# Python 3 program to find sum of numbers from
# 1 to N which are divisible by X or Y
from math import ceil, floor
 
# Function to calculate the sum
# of numbers divisible by X or Y
def sum(N, X, Y):
    S1 = floor(floor(N / X) * floor(2 * X +
               floor(N / X - 1) * X) / 2)
    S2 = floor(floor(N / Y)) * floor(2 * Y +
               floor(N / Y - 1) * Y) / 2
    S3 = floor(floor(N / (X * Y))) * floor (2 * (X * Y) +
               floor(N / (X * Y) - 1) * (X * Y))/ 2
 
    return S1 + S2 - S3
 
# Driver code
if __name__ == '__main__':
    N = 14
    X = 3
    Y = 5
 
    print(int(sum(N, X, Y)))
 
# This code is contributed by
# Surendra_Gangwar

// C# program to find sum of numbers from
// 1 to N which are divisible by X or Y
  
using System;
public class GFG{
      
    // Function to calculate the sum
    // of numbers divisible by X or Y
    static int sum(int N, int X, int Y)
    {
        int S1, S2, S3;
      
        S1 = ((N / X)) * (2 * X + (N / X - 1) * X) / 2;
        S2 = ((N / Y)) * (2 * Y + (N / Y - 1) * Y) / 2;
        S3 = ((N / (X * Y))) * (2 * (X * Y)
                          + (N / (X * Y) - 1) * (X * Y))/ 2;
      
        return S1 + S2 - S3;
    }
      
    // Driver code
    public static void Main()
    {
        int N = 14;
        int X = 3, Y = 5;
      
        Console.Write(sum(N, X, Y));
      
    }
     
}

<?php
// PHP program to find sum of numbers from
// 1 to N which are divisible by X or Y
// Function to calculate the sum
// of numbers divisible by X or Y
function sum($N, $X, $Y)
{
    $S1; $S2; $S3;
 
    $S1 = floor(((int)$N / $X)) * (2 * $X + (int)((int)$N / $X - 1) * $X) / 2;
    $S2 = floor(((int)$N / $Y)) * (2 * $Y + (int)((int)$N / $Y - 1) * $Y) / 2;
    $S3 = floor(((int)$N / ($X * $Y))) * (2 * ($X * $Y)
                    + ((int)$N / ($X * $Y) - 1) * (int)($X * $Y))/ 2;
 
    return ceil($S1 + ($S2 - $S3));
}
 
// Driver code
    $N = 14;
    $X = 3;
    $Y = 5;
 
    echo  sum($N, $X, $Y);
 
#This code is contributed by ajit.
?>

<script>
// javascript program to find sum of numbers from
// 1 to N which are divisible by X or Y
 
     
// Function to calculate the sum
// of numbers divisible by X or Y
function sum(N , X , Y)
{
    var S1, S2, S3;
 
    S1 = (parseInt(N / X)) * (2 * X + parseInt(N / X - 1) * X) / 2;
    S2 = (parseInt(N / Y)) * (2 * Y + parseInt(N / Y - 1) * Y) / 2;
    S3 = (parseInt(N / (X * Y))) * (2 * (X * Y)
                      + parseInt(N / (X * Y) - 1) * (X * Y))/ 2;
 
    return S1 + S2 - S3;
}
 
// Driver code
var N = 14;
var X = 3, Y = 5;
 
document.write(sum(N, X, Y));
 
// This code is contributed by Princi Singh
</script>

// C program to find sum of numbers from
// 1 to N which are divisible by X or Y
#include <stdio.h>
 
// Function to calculate the sum
// of numbers divisible by X or Y
int sum(int N, int X, int Y)
{
    int S1, S2, S3;
 
    S1 = ((N / X)) * (2 * X + (N / X - 1) * X) / 2;
    S2 = ((N / Y)) * (2 * Y + (N / Y - 1) * Y) / 2;
    S3 = ((N / (X * Y))) * (2 * (X * Y) + (N / (X * Y) - 1) * (X * Y))/ 2;
    return S1 + S2 - S3;
}
 
// Driver code
int main()
{
    int N = 14;
    int X = 3, Y = 5;
    printf("%d ",sum(N, X, Y));
    return 0;
}

45

Complejidad de tiempo : O(1)

Espacio Auxiliar: O(1)