Encuentre el valor máximo posible para la función periódica dada

Dados tres números A, B y N , la tarea es encontrar el valor máximo posible de piso (A * x / B) – A * piso (x / b) donde x es un número entero no negativo menor o igual que N. Aquí piso (T) = denota el mayor entero no mayor que el número real T (función GIF). 
Restricciones: 1 ≤ A ≤ 10 ⁶ , 1 ≤ B ≤ 10 ¹² , 1 ≤ N ≤ 10 ¹² . Todos los valores en la entrada son enteros.

Entrada: A = 5, B = 7, N = 4 
Salida: 2 
Explicación: 
El valor máximo se obtiene para el valor x = 3. Al sustituir este valor en la ecuación: 
piso((5 * 3)/7) – ( 5 * piso (3 / 7)) = piso (2.1) – 0 = 2.

Entrada: A = 11, B = 10, N = 9 
Salida: 9  

Enfoque ingenuo: el enfoque ingenuo para este problema es considerar todos los números posibles del 1 al N y calcular el valor máximo posible. 

Complejidad temporal: O(N). 

Enfoque Eficiente: La idea es hacer una observación sobre la función f(x) = piso(A * x / B) – A * piso(x / B) . 

• Podemos observar que la función dada es una función periódica. Esto puede ser probado por:

f(x + B) = piso(A * (x + B)/B) – A * piso((x + B)/B) 
=> f(x + B) = piso((A * x / B) + A) – A * piso((x /B) + 1)
Por la propiedad de la función piso, piso(x + Entero) = Entero + piso(x). 
=> f(x + B) = piso(A * x / B) – A * piso(x / B) = f(x)  

• Por lo tanto, podemos concluir que 0 ≤ x ≤ B. Sin embargo, si x = B, f(x) = 0. Entonces, lo excluimos y obtenemos 0 ≤ x ≤ B-1.
• Sin embargo, también debemos considerar la condición x ≤ N. Como piso(x) es una función monótonamente no decreciente, debemos incorporar lo mejor de ambos rangos.
• Por lo tanto, el valor máximo de f(x) se obtiene cuando x = min(B – 1, N) .

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

// C++ Program to find the maximum
// possible value for the given function
 
#include <iostream>
using namespace std;
 
// Function to return the maximum
// value of f(x)
int floorMax(int A, int B, int N)
{
    int x = min(B - 1, N);
 
    return (A * x) / B;
}
 
// Driver code
int main()
{
    int A = 11, B = 10, N = 9;
 
    cout << floorMax(A, B, N);
    return 0;
}

// Java program to find the maximum
// possible value for the given function
class GFG{
     
// Function to return the maximum
// value of f(x)
public static int floorMax(int A, int B, int N)
{
    int x = Math.min(B - 1, N);
 
    return (A * x) / B;
}
 
// Driver Code
public static void main(String[] args)
{
    int A = 11, B = 10, N = 9;
     
    System.out.println(floorMax(A, B, N));
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program to find the maximum
# possible value for the given function
  
# Function to return the maximum
# value of f(x)
def floorMax(A, B, N):
     
    x = min(B - 1, N)
  
    return (A * x) // B
  
# Driver code
A = 11
B = 10
N = 9
  
print(floorMax(A, B, N))
 
# This code is contributed by code_hunt

// C# program to find the maximum
// possible value for the given function        
using System;
using System.Collections.Generic;
 
class GFG{        
             
// Function to return the maximum
// value of f(x)
static int floorMax(int A, int B, int N)
{
    int x = Math.Min(B - 1, N);
 
    return (A * x) / B;
}    
         
// Driver Code        
public static void Main (string[] args)
{        
    int A = 11, B = 10, N = 9;
 
    Console.Write(floorMax(A, B, N));
}        
}
 
// This code is contributed by rutvik_56

<script>
 
// Javascript program to find the maximum
// possible value for the given function
 
// Function to return the maximum
// value of f(x)
function floorMax(A, B, N)
{
    let x = Math.min(B - 1, N);
  
    return Math.floor((A * x) / B);
}
 
// Driver Code
     
   let A = 11, B = 10, N = 9;
      
   document.write(floorMax(A, B, N));
       
</script>

9

Complejidad de tiempo: O(1)