Programa para encontrar el término N-ésimo divisible por a o b

Dados dos enteros  y  . La tarea es encontrar el término N-ésimo que sea divisible por o  por  .
Ejemplos: 
 

Input : a = 2, b = 5, N = 10
Output : 16

Input : a = 3, b = 7, N = 25
Output : 57

Enfoque ingenuo: un enfoque simple es atravesar todos los términos a partir de 1 hasta que encontremos el término N-ésimo deseado que es divisible por o  por  . Esta solución tiene una complejidad temporal de O(N).
Enfoque eficiente: la idea es utilizar la búsqueda binaria . Aquí podemos calcular cuántos números del 1 al  son divisibles por a o b usando la fórmula:

Todos los múltiplos de mcm(a, b) serán divisibles por ambos  ,  por lo que debemos eliminar estos términos. Ahora, si el número de términos divisibles es menor que N, aumentaremos la posición baja de la búsqueda binaria; de lo contrario, disminuiremos hasta que el número de términos divisibles sea igual a N.
A continuación se muestra la implementación de la idea anterior: 
 

// C++ program to find nth term
// divisible by a or b
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return
// gcd of a and b
int gcd(int a, int b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
// Function to calculate how many numbers
// from 1 to num are divisible by a or b
int divTermCount(int a, int b, int lcm, int num)
{
    // calculate number of terms divisible by a and
    // by b then, remove the terms which is are
    // divisible by both a and b
    return num / a + num / b - num / lcm;
}
 
// Binary search to find the nth term
// divisible by a or b
int findNthTerm(int a, int b, int n)
{
    // set low to 1 and high to max(a, b)*n, here
    // we have taken high as 10^18
    int low = 1, high = INT_MAX, mid;
    int lcm = (a * b) / gcd(a, b);
 
    while (low < high) {
        mid = low + (high - low) / 2;
 
        // if the current term is less than
        // n then we need to increase low
        // to mid + 1
        if (divTermCount(a, b, lcm, mid) < n)
            low = mid + 1;
 
        // if current term is greater than equal to
        // n then high = mid
        else
            high = mid;
    }
 
    return low;
}
 
// Driver code
int main()
{
    int a = 2, b = 5, n = 10;
    cout << findNthTerm(a, b, n) << endl;
 
    return 0;
}

// Java program to find nth term
// divisible by a or b
class GFG
{
// Function to return
// gcd of a and b
static int gcd(int a, int b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
// Function to calculate how many numbers
// from 1 to num are divisible by a or b
static int divTermCount(int a, int b,
                        int lcm, int num)
{
    // calculate number of terms
    // divisible by a and by b then,
    // remove the terms which is are
    // divisible by both a and b
    return num / a + num / b - num / lcm;
}
 
// Binary search to find the
// nth term divisible by a or b
static int findNthTerm(int a, int b, int n)
{
    // set low to 1 and high to max(a, b)*n, 
    // here we have taken high as 10^18
    int low = 1, high = Integer.MAX_VALUE, mid;
    int lcm = (a * b) / gcd(a, b);
 
    while (low < high)
    {
        mid = low + (high - low) / 2;
 
        // if the current term is less
        // than n then we need to increase
        // low to mid + 1
        if (divTermCount(a, b, lcm, mid) < n)
            low = mid + 1;
 
        // if current term is greater
        // than equal to n then high = mid
        else
            high = mid;
    }
 
    return low;
}
 
// Driver code
public static void main (String[] args)
{
    int a = 2, b = 5, n = 10;
    System.out.println(findNthTerm(a, b, n));
}
}
 
// This code is contributed by Smitha

# Python 3 program to find nth term
# divisible by a or b
import sys
 
# Function to return gcd of a and b
def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)
 
# Function to calculate how many numbers
# from 1 to num are divisible by a or b
def divTermCount(a, b, lcm, num):
 
    # calculate number of terms divisible
    # by a and by b then, remove the terms
    # which are divisible by both a and b
    return num // a + num // b - num // lcm
 
# Binary search to find the nth term
# divisible by a or b
def findNthTerm(a, b, n):
 
    # set low to 1 and high to max(a, b)*n,
    # here we have taken high as 10^18
    low = 1; high = sys.maxsize
    lcm = (a * b) // gcd(a, b)
    while low < high:
        mid = low + (high - low) // 2
 
        # if the current term is less
        # than n then we need to increase 
        # low to mid + 1
        if divTermCount(a, b, lcm, mid) < n:
            low = mid + 1
 
        # if current term is greater
        # than equal to n then high = mid
        else:
            high = mid
    return low
 
# Driver code
a = 2; b = 5; n = 10
print(findNthTerm(a, b, n))
 
# This code is contributed by Shrikant13

// C# program to find nth term
// divisible by a or b
using System;
 
class GFG
{
// Function to return gcd of a and b
static int gcd(int a, int b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
// Function to calculate how many numbers
// from 1 to num are divisible by a or b
static int divTermCount(int a, int b,
                        int lcm, int num)
{
    // calculate number of terms
    // divisible by a and by b then,
    // remove the terms which is are
    // divisible by both a and b
    return num / a + num / b - num / lcm;
}
 
// Binary search to find the
// nth term divisible by a or b
static int findNthTerm(int a, int b, int n)
{
    // set low to 1 and high to max(a, b)*n,
    // here we have taken high as 10^18
    int low = 1, high = int.MaxValue, mid;
    int lcm = (a * b) / gcd(a, b);
 
    while (low < high)
    {
        mid = low + (high - low) / 2;
 
        // if the current term is less
        // than n then we need to increase
        // low to mid + 1
        if (divTermCount(a, b, lcm, mid) < n)
            low = mid + 1;
 
        // if current term is greater
        // than equal to n then high = mid
        else
            high = mid;
    }
 
    return low;
}
 
// Driver code
static public void Main ()
{
    int a = 2, b = 5, n = 10;
    Console.WriteLine(findNthTerm(a, b, n));
}
}
 
// This code is contributed by Sach_Code

<script>
 
// JavaScript program to find nth term
// divisible by a or b
 
// Function to return
// gcd of a and b
function gcd(a , b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
// Function to calculate how many numbers
// from 1 to num are divisible by a or b
function divTermCount(a , b, lcm , num)
{
    // calculate number of terms
    // divisible by a and by b then,
    // remove the terms which is are
    // divisible by both a and b
    return parseInt(num / a) +
    parseInt(num / b) - parseInt(num / lcm);
}
 
// Binary search to find the
// nth term divisible by a or b
function findNthTerm(a , b , n)
{
    // set low to 1 and high to max(a, b)*n, 
    // here we have taken high as 10^18
    var low = 1, high = Number.MAX_VALUE, mid;
    var lcm = parseInt((a * b) / gcd(a, b));
 
    while (low < high)
    {
        mid = low + parseInt((high - low) / 2);
 
        // if the current term is less
        // than n then we need to increase
        // low to mid + 1
        if (divTermCount(a, b, lcm, mid) < n)
            low = mid + 1;
 
        // if current term is greater
        // than equal to n then high = mid
        else
            high = mid;
    }
 
    return low;
}
 
// Driver code
var a = 2, b = 5, n = 10;
document.write(findNthTerm(a, b, n));
 
 
// This code is contributed by Amit Katiyar
 
</script>

16

Hay un tercer enfoque que toma O(log(min(a, b))) .

Complejidad de tiempo en el peor de los casos: O (log (min (a, b)))

#include<bits/stdc++.h>
using namespace std;
 
// if you do not consider multiples of both a and b in the count;;;
long long gcd(long long a, long long b){
    long long temp = a+b;
    a = (a>b)?a:b;
    b = temp - a;
 
    if (a%b == 0){
        return b;
    } return gcd(b, a%b);
}
 
long long trUE_n_Smallest_AB(long long a, long long b, long long n){
    if (n*a < b){return n*a;}
    if (n*a == b){return a*(n+1);}
    long long g = gcd(a, b);
    a/=g;
    b/=g;
    long long filler = 0;
    long long sum = 0;
    if (n > a+b-2) {
        sum = a + b -2; filler = (n/sum)*a*b; n %= sum;}
    if (n == 0){
        return g*(filler - a);
    }
    long long rat_a = (n*b)/(a+b);
    long long rat_b = (n*a)/(a+b);
    if(a*rat_a > b*rat_b){
        return g*(min(a*rat_a+a ,b*rat_b + b) + filler);
    } else {
        return g*(a*rat_a + a + filler);
    }
}
 
// if you do consider multiples of both a and b in the count;;;
long long boTH_trUE_n_Smallest_AB(long long a, long long b, long long n){
    if (n*a <= b){return n*a;}
    long long g = gcd(a, b);
    a/=g;
    b/=g;
    long long filler = 0;
    long long sum = 0;
    if (n > a+b - 1) {
        sum = a + b - 1; filler = (n/sum)*a*b; n %= sum;}
    if (n == 0){
        return g*(filler - a);
    }
    long long rat_a = (n*b)/(a+b);
    long long rat_b = (n*a)/(a+b);
    if(a*rat_a > b*rat_b){
        return g*(min(a*rat_a+a ,b*rat_b + b) + filler);
    } else {
        return g*(a*rat_a + a + filler);
    }
}
 
int main(void) {
 
    long long a = 2, b = 5, n = 10;
    long long true_a = min(a, b);
    long long true_b = max(a, b);
 
    // long answer = binaryApproach(true_a, true_b, n, 0, n*true_a);
    long long answer = boTH_trUE_n_Smallest_AB(true_a, true_b, n);
    cout << answer << endl;
    return 0;
}
 
// This code is contributed by Rishabh.

import java.io.*;
// import java.util.Scanner;
 
class GFG {
    // if you do not consider multiples of both a and b in the count;;;
  public static long gcd(long a, long b){
      long temp = a+b;
      a = (a>b)?a:b;
      b = temp - a;
 
      if (a%b == 0){
          return b;
      } return gcd(b, a%b);
  }
   
  public static long trUE_n_Smallest_AB(long a, long b, long n){
        if (n*a < b){return n*a;}
        if (n*a == b){return a*(n+1);}
        long g = gcd(a, b);
        a/= g;
        b/= g;
 
        long filler = 0;
        long sum = 0;
        if (n > a+b-2) {
            sum = a + b -2; filler = (n/sum)*a*b; n %= sum;}
        if (n == 0){
            return g*(filler - a);
        }
        long rat_a = (n*b)/(a+b);
        long rat_b = (n*a)/(a+b);
        if(a*rat_a > b*rat_b){
            return g*(Math.min(a*rat_a+a ,b*rat_b + b) + filler);
        } else {
            return g*(a*rat_a + a + filler);
        }
    }
 
    // if you do consider multiples of both a and b int the count;;;
    public static long boTH_trUE_n_Smallest_AB(long a, long b, long n){
        if (n*a <= b){return n*a;}
          long g = gcd(a, b);
          a/=g;
          b/=g;
        long filler = 0;
        long sum = 0;
        if (n > a+b - 1) {
            sum = a + b - 1; filler = (n/sum)*a*b; n %= sum;}
        if (n == 0){
            return g*(filler - a);
        }
        long rat_a = (n*b)/(a+b);
        long rat_b = (n*a)/(a+b);
        if(a*rat_a > b*rat_b){
            return g*(Math.min(a*rat_a+a ,b*rat_b + b) + filler);
        } else {
            return g*(a*rat_a + a + filler);
        }
    }
 
    public static void main(String[] args) {
   //     Scanner sc = new Scanner(System.in);
   //     long a = sc.nextLong(), b = sc.nextLong(), n = sc.nextLong();
   //     sc.close();
          long a = 2, b = 5, n = 10;
        long true_a = Math.min(a, b);
        long true_b = Math.max(a, b);
        // long answer = trUE_n_Smallest_AB(true_a, true_b, n);
        long answer = boTH_trUE_n_Smallest_AB(true_a, true_b, n);
        System.out.println(answer);
    }
}
 
 
// This code is contributed by Rishabh.

# if you do not consider multiples of both a and b in the count;;;
def gcd(a, b):
  temp = a+b
  if (a<b):
    a = b
  b = temp -a
  if (a%b == 0):
    return b
  return gcd(b, a%b)
 
def trUE_n_Smallest_AB(a, b, n):
    if (n*a < b):
        return n*a
    if (n*a == b):
        return a*(n+1)
    g = gcd(a, b)
    a//=g
    b//=g
 
    filler = 0;
    sum = 0;
    if (n > a+b-2):
        sum = a + b -2; filler = (n//sum)*a*b; n %= sum
    if (n == 0):
        return g*(filler - a)
    rat_a = (n*b)//(a+b)
    rat_b = (n*a)//(a+b)
    if(a*rat_a > b*rat_b):
        return g*(min(a*rat_a+a ,b*rat_b + b) + filler)
    else:
        return g*(a*rat_a + a + filler)
 
# if you do consider multiples of both a and b in the count;;;
def boTH_trUE_n_Smallest_AB(a, b, n):
    if (n*a <= b):
        return n*a
    g = gcd(a, b)
    a//=g
    b//=g
    filler = 0
    sum = 0
    if (n > a+b - 1):
        sum = a + b - 1; filler = (n//sum)*a*b; n %= sum
    if (n == 0):
        return g*(filler - a)
    rat_a = (n*b)//(a+b)
    rat_b = (n*a)//(a+b)
    if(a*rat_a > b*rat_b):
        return g*(min(a*rat_a+a ,b*rat_b + b) + filler)
    else:
        return g*(a*rat_a + a + filler)
 
a = 2; b = 5 ; n = 10
true_a = min(a, b)
true_b = max(a, b)
# answer = trUE_n_Smallest_AB(true_a, true_b, n);
answer = boTH_trUE_n_Smallest_AB(true_a, true_b, n)
print(answer)
 
# This code is contributed by Rishabh.

#include<stdio.h>
long long min(long long a, long long b) {return (a < b) ? a : b;}
long long max(long long a, long long b) {return (a > b) ? a : b;}
 
// if you do not consider multiples of both a and b in the count;;;
long long gcd(long long a, long long b){
    long long temp = a+b;
    a = (a>b)?a:b;
    b = temp - a;
 
    if (a%b == 0){
        return b;
    } return gcd(b, a%b);
}
 
long long trUE_n_Smallest_AB(long long a, long long b, long long n){
    if (n*a < b){return n*a;}
    if (n*a == b){return a*(n+1);}
      long long g = gcd(a, b);
      a/=g;
    b/=g;
 
    long long filler = 0;
    long long sum = 0;
    if (n > a+b-2) {
        sum = a + b -2; filler = (n/sum)*a*b; n %= sum;}
    if (n == 0){
        return g*(filler - a);
    }
    long long rat_a = (n*b)/(a+b);
    long long rat_b = (n*a)/(a+b);
    if(a*rat_a > b*rat_b){
        return g*(min(a*rat_a+a ,b*rat_b + b) + filler);
    } else {
        return g*(a*rat_a + a + filler);
    }
}
 
// if you do consider multiples of both a and b in the count;;;
long long boTH_trUE_n_Smallest_AB(long long a, long long b, long long n){
    if (n*a <= b){return n*a;}
      long long g = gcd(a, b);
      a/=g;
      b/=g;
    long long filler = 0;
    long long sum = 0;
    if (n > a+b - 1) {
        sum = a + b - 1; filler = (n/sum)*a*b; n %= sum;}
    if (n == 0){
        return g*(filler - a);
    }
    long long rat_a = (n*b)/(a+b);
    long long rat_b = (n*a)/(a+b);
    if(a*rat_a > b*rat_b){
        return g*(min(a*rat_a+a ,b*rat_b + b) + filler);
    } else {
        return g*(a*rat_a + a + filler);
    }
}
 
int main(void) {
    long long a = 2, b = 5, n = 10;
    long long true_a = min(a, b);
    long long true_b = max(a, b);
    // long long answer = trUE_n_Smallest_AB(true_a, true_b, n, 0, n*true_a);
    long long answer = boTH_trUE_n_Smallest_AB(true_a, true_b, n);
    printf("%lli\n", answer);
    return 0;
}
 
// This code is contributed by Rishabh.

16

Este enfoque usa la densidad de a y b, y resuelve para n.

El enfoque toma solo el tiempo O (log (min (a, b))) como solo operaciones matemáticas simples (sumar, restar, multiplicar y dividir, mínimo/máximo de 2 números -> todo O (1) y operación mcd -> O (log(min(a, b)))) se utilizan aquí.

NOTA SOBRE Módulo(“%”): a-=b*(a/b) es equivalente a a%=b, por lo que puede suponer que también es O(1).