Maximizar el beneficio cuando la divisibilidad entre dos números tiene beneficios asociados

Dados cinco números enteros N , A , B , X e Y . La tarea es encontrar el beneficio máximo obtenido de los números del rango [1, N] . Si un número positivo es divisible por A , la ganancia aumenta en X y si un número positivo es divisible por B ,  la ganancia aumenta en Y.
Nota: Las ganancias de un número positivo se pueden agregar como máximo una vez.
Ejemplos: 
 

Entrada: N = 3, A = 1, B = 2, X = 3, Y = 4 
Salida: 10 
1, 2 y 3 son divisibles por A. 
2 es el único número en el rango dado que es divisible por B. 
2 es divisible por A y B. 
1 y 3 pueden dividirse entre A para obtener una ganancia de 2 * 3 = 6 
2 pueden dividirse entre B para obtener una ganancia de 1 * 4 = 4 
2 es divisible por ambos pero en orden para maximizar la ganancia se divide por B en lugar de A.
Entrada: N = 6, A = 6, B = 2, X = 8, Y = 2 
Salida: 12 
 

Enfoque: es fácil ver que podemos dividir un número tanto con A como con B solo si el número es un múltiplo de mcm(A, B) . Obviamente, ese número debe dividirse con el número que da más ganancias. 
Entonces la respuesta es igual a X * (N / A) + Y * (N / B) – min(X, Y) * (N / lcm(A, B)) .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum profit
int maxProfit(int n, int a, int b, int x, int y)
{
    int res = x * (n / a);
    res += y * (n / b);
 
    // min(x, y) * n / lcm(a, b)
    res -= min(x, y) * (n / ((a * b) / __gcd(a, b)));
    return res;
}
 
// Driver code
int main()
{
    int n = 6, a = 6, b = 2, x = 8, y = 2;
    cout << maxProfit(n, a, b, x, y);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
static int __gcd(int a, int b)
{
    if (b == 0)
        return a;
    return __gcd(b, a % b);
     
}
 
// Function to return the maximum profit
static int maxProfit(int n, int a, int b,
                            int x, int y)
{
    int res = x * (n / a);
    res += y * (n / b);
 
    // min(x, y) * n / lcm(a, b)
    res -= Math.min(x, y) * (n / ((a * b) / __gcd(a, b)));
    return res;
}
 
// Driver code
public static void main (String[] args)
{
    int n = 6, a = 6, b = 2, x = 8, y = 2;
    System.out.println(maxProfit(n, a, b, x, y));
}
}
 
// This code is contributed by mits

# Python3 implementation of the approach
from math import gcd
 
# Function to return the maximum profit
def maxProfit(n, a, b, x, y) :
     
    res = x * (n // a);
    res += y * (n // b);
 
    # min(x, y) * n / lcm(a, b)
    res -= min(x, y) * (n // ((a * b) //
                           gcd(a, b)));
    return res;
 
# Driver code
if __name__ == "__main__" :
 
    n = 6 ;a = 6; b = 2; x = 8; y = 2;
     
    print(maxProfit(n, a, b, x, y));
     
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
 
class GFG
{
 
static int __gcd(int a, int b)
{
    if (b == 0)
        return a;
    return __gcd(b, a % b);
     
}
 
// Function to return the maximum profit
static int maxProfit(int n, int a, int b, int x, int y)
{
    int res = x * (n / a);
    res += y * (n / b);
 
    // min(x, y) * n / lcm(a, b)
    res -= Math.Min(x, y) * (n / ((a * b) / __gcd(a, b)));
    return res;
}
 
// Driver code
static void Main()
{
    int n = 6, a = 6, b = 2, x = 8, y = 2;
    Console.WriteLine(maxProfit(n, a, b, x, y));
}
}
 
// This code is contributed by mits

<?php
// PHP implementation of the approach
function __gcd($a, $b)
{
    if ($b == 0)
        return $a;
    return __gcd($b, $a % $b);
     
}
 
// Function to return the maximum profit
function maxProfit($n, $a, $b, $x, $y)
{
    $res = $x * ($n / $a);
    $res += $y * ($n / $b);
 
    // min(x, y) * n / lcm(a, b)
    $res -= min($x, $y) * ($n /
              (($a * $b) / __gcd($a, $b)));
    return $res;
}
 
// Driver code
$n = 6;
$a = 6;
$b = 2;
$x = 8;
$y = 2;
print(maxProfit($n, $a, $b, $x, $y));
 
// This code is contributed by mits
?>

<script>
 
// JavaScript implementation of the approach
function __gcd(a, b)
{
    if (b == 0)
        return a;
    return __gcd(b, a % b);
       
}
 
// Function to return the maximum profit
 
function maxProfit(n, a, b, x, y)
{
    let res = x * Math.floor(n / a);
    res += y * Math.floor(n / b);
 
    // min(x, y) * n / lcm(a, b)
    res -= Math.min(x, y) * (n / ((a * b) / __gcd(a, b)));
    return res;
}
 
// Driver code
    let n = 6, a = 6, b = 2, x = 8, y = 2;
    document.write(maxProfit(n, a, b, x, y));
 
 
// This article is contributed by Surbhi Tyagi.
 
</script>

12

Complejidad del tiempo: O(log(min(a, b)))

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