Dados cuatro enteros A , B , C y K . Suponga que todos los múltiplos de A , B y C están almacenados en un conjunto en orden ordenado sin duplicados, ahora la tarea es encontrar el K -ésimo elemento de ese conjunto.
Ejemplos:
Entrada: A = 1, B = 2, C = 3, K = 4
Salida: 4
El conjunto requerido es {1, 2, 3, 4, 5, …}
Entrada: A = 2, B = 4, C = 5 , K = 5
Salida: 8
Enfoque: La búsqueda binaria se puede utilizar aquí en K para encontrar el número K en el conjunto. Encontremos el K -ésimo número si este fuera un múltiplo de A.
Aplique la búsqueda binaria en los múltiplos de A , comenzando desde 1 hasta K (ya que puede haber K múltiplos máximos de A para encontrar el número K en el conjunto requerido).
Ahora, para un valor mid , el múltiplo requerido de A será A * mid (digamos X) . Ahora la tarea es encontrar si este es elK -ésimo número del conjunto requerido. Se puede encontrar como se muestra a continuación:
Hallar el número de múltiplos de A menor que X , digamos A1
Hallar el número de múltiplos de B menor que X , digamos B1
Hallar el número de múltiplos de C menor que X , digamos C1
Hallar el número de múltiplos de mcm(A, B) (Divisible por A y B) menor que X diga AB1
Halle el número de múltiplos de mcm(B, C) menor que X diga BC1
Halle el número de múltiplos de mcm(C, A) menor que X diga CA1
Encuentra el número de múltiplos de mcm(A, B, C) menos que X , digamos ABC1
Ahora, el conteo de números en el conjunto requerido menor que X será A1 + B1 + C1 – AB1 – BC1 – CA1 + ABC1 por el principio de Inclusión y Exclusión .
Si cuenta = K – 1 , entonces X es la respuesta requerida.
Si cuenta < K – 1, entonces ese múltiplo es mayor que X implica establecer inicio = medio + 1 , de lo contrario establecer final = medio – 1 .
Realice los mismos pasos (si el número K no es un múltiplo de A ) para B y luego para C.
Desde el KthEl número está destinado a ser un múltiplo de A , B o C , estas tres búsquedas binarias definitivamente devolverán el resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
// Function to return the
// GCD of A and B
int gcd(int A, int B)
{
if (B == 0)
return A;
return gcd(B, A % B);
}
// Function to return the
// LCM of A and B
int lcm(int A, int B)
{
return (A * B) / gcd(A, B);
}
// Function to return the Kth element from
// the required set if it a multiple of A
int checkA(int A, int B, int C, int K)
{
// Start and End for Binary Search
int start = 1;
int end = K;
// If no answer found return -1
int ans = -1;
while (start <= end) {
int mid = (start + end) / 2;
int value = A * mid;
int divA = mid - 1;
int divB = (value % B == 0) ? value / B - 1
: value / B;
int divC = (value % C == 0) ? value / C - 1
: value / C;
int divAB = (value % lcm(A, B) == 0)
? value / lcm(A, B) - 1
: value / lcm(A, B);
int divBC = (value % lcm(C, B) == 0)
? value / lcm(C, B) - 1
: value / lcm(C, B);
int divAC = (value % lcm(A, C) == 0)
? value / lcm(A, C) - 1
: value / lcm(A, C);
int divABC = (value % lcm(A, lcm(B, C)) == 0)
? value / lcm(A, lcm(B, C)) - 1
: value / lcm(A, lcm(B, C));
// Inclusion and Exclusion
int elem = divA + divB + divC - divAC
- divBC - divAB + divABC;
if (elem == (K - 1)) {
ans = value;
break;
}
// Multiple should be smaller
else if (elem > (K - 1)) {
end = mid - 1;
}
// Multiple should be bigger
else {
start = mid + 1;
}
}
return ans;
}
// Function to return the Kth element from
// the required set if it a multiple of B
int checkB(int A, int B, int C, int K)
{
// Start and End for Binary Search
int start = 1;
int end = K;
// If no answer found return -1
int ans = -1;
while (start <= end) {
int mid = (start + end) / 2;
int value = B * mid;
int divB = mid - 1;
int divA = (value % A == 0) ? value / A - 1
: value / A;
int divC = (value % C == 0) ? value / C - 1
: value / C;
int divAB = (value % lcm(A, B) == 0)
? value / lcm(A, B) - 1
: value / lcm(A, B);
int divBC = (value % lcm(C, B) == 0)
? value / lcm(C, B) - 1
: value / lcm(C, B);
int divAC = (value % lcm(A, C) == 0)
? value / lcm(A, C) - 1
: value / lcm(A, C);
int divABC = (value % lcm(A, lcm(B, C)) == 0)
? value / lcm(A, lcm(B, C)) - 1
: value / lcm(A, lcm(B, C));
// Inclusion and Exclusion
int elem = divA + divB + divC - divAC
- divBC - divAB + divABC;
if (elem == (K - 1)) {
ans = value;
break;
}
// Multiple should be smaller
else if (elem > (K - 1)) {
end = mid - 1;
}
// Multiple should be bigger
else {
start = mid + 1;
}
}
return ans;
}
// Function to return the Kth element from
// the required set if it a multiple of C
int checkC(int A, int B, int C, int K)
{
// Start and End for Binary Search
int start = 1;
int end = K;
// If no answer found return -1
int ans = -1;
while (start <= end) {
int mid = (start + end) / 2;
int value = C * mid;
int divC = mid - 1;
int divB = (value % B == 0) ? value / B - 1
: value / B;
int divA = (value % A == 0) ? value / A - 1
: value / A;
int divAB = (value % lcm(A, B) == 0)
? value / lcm(A, B) - 1
: value / lcm(A, B);
int divBC = (value % lcm(C, B) == 0)
? value / lcm(C, B) - 1
: value / lcm(C, B);
int divAC = (value % lcm(A, C) == 0)
? value / lcm(A, C) - 1
: value / lcm(A, C);
int divABC = (value % lcm(A, lcm(B, C)) == 0)
? value / lcm(A, lcm(B, C)) - 1
: value / lcm(A, lcm(B, C));
// Inclusion and Exclusion
int elem = divA + divB + divC - divAC
- divBC - divAB + divABC;
if (elem == (K - 1)) {
ans = value;
break;
}
// Multiple should be smaller
else if (elem > (K - 1)) {
end = mid - 1;
}
// Multiple should be bigger
else {
start = mid + 1;
}
}
return ans;
}
// Function to return the Kth element from
// the set of multiples of A, B and C
int findKthMultiple(int A, int B, int C, int K)
{
// Apply binary search on the multiples of A
int res = checkA(A, B, C, K);
// If the required element is not a
// multiple of A then the multiples
// of B and C need to be checked
if (res == -1)
res = checkB(A, B, C, K);
// If the required element is neither
// a multiple of A nor a multiple
// of B then the multiples of C
// need to be checked
if (res == -1)
res = checkC(A, B, C, K);
return res;
}
// Driver code
int main()
{
int A = 2, B = 4, C = 5, K = 5;
cout << findKthMultiple(A, B, C, K);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
// Function to return the
// GCD of A and B
static int gcd(int A, int B)
{
if (B == 0)
return A;
return gcd(B, A % B);
}
// Function to return the
// LCM of A and B
static int lcm(int A, int B)
{
return (A * B) / gcd(A, B);
}
// Function to return the Kth element from
// the required set if it a multiple of A
static int checkA(int A, int B, int C, int K)
{
// Start and End for Binary Search
int start = 1;
int end = K;
// If no answer found return -1
int ans = -1;
while (start <= end)
{
int mid = (start + end) / 2;
int value = A * mid;
int divA = mid - 1;
int divB = (value % B == 0) ? value / B - 1
: value / B;
int divC = (value % C == 0) ? value / C - 1
: value / C;
int divAB = (value % lcm(A, B) == 0) ?
value / lcm(A, B) - 1 :
value / lcm(A, B);
int divBC = (value % lcm(C, B) == 0) ?
value / lcm(C, B) - 1 :
value / lcm(C, B);
int divAC = (value % lcm(A, C) == 0) ?
value / lcm(A, C) - 1 :
value / lcm(A, C);
int divABC = (value % lcm(A, lcm(B, C)) == 0) ?
value / lcm(A, lcm(B, C)) - 1 :
value / lcm(A, lcm(B, C));
// Inclusion and Exclusion
int elem = divA + divB + divC - divAC -
divBC - divAB + divABC;
if (elem == (K - 1))
{
ans = value;
break;
}
// Multiple should be smaller
else if (elem > (K - 1))
{
end = mid - 1;
}
// Multiple should be bigger
else
{
start = mid + 1;
}
}
return ans;
}
// Function to return the Kth element from
// the required set if it a multiple of B
static int checkB(int A, int B, int C, int K)
{
// Start and End for Binary Search
int start = 1;
int end = K;
// If no answer found return -1
int ans = -1;
while (start <= end)
{
int mid = (start + end) / 2;
int value = B * mid;
int divB = mid - 1;
int divA = (value % A == 0) ? value / A - 1
: value / A;
int divC = (value % C == 0) ? value / C - 1
: value / C;
int divAB = (value % lcm(A, B) == 0) ?
value / lcm(A, B) - 1 :
value / lcm(A, B);
int divBC = (value % lcm(C, B) == 0) ?
value / lcm(C, B) - 1 :
value / lcm(C, B);
int divAC = (value % lcm(A, C) == 0) ?
value / lcm(A, C) - 1 :
value / lcm(A, C);
int divABC = (value % lcm(A, lcm(B, C)) == 0) ?
value / lcm(A, lcm(B, C)) - 1 :
value / lcm(A, lcm(B, C));
// Inclusion and Exclusion
int elem = divA + divB + divC - divAC
- divBC - divAB + divABC;
if (elem == (K - 1))
{
ans = value;
break;
}
// Multiple should be smaller
else if (elem > (K - 1))
{
end = mid - 1;
}
// Multiple should be bigger
else
{
start = mid + 1;
}
}
return ans;
}
// Function to return the Kth element from
// the required set if it a multiple of C
static int checkC(int A, int B, int C, int K)
{
// Start and End for Binary Search
int start = 1;
int end = K;
// If no answer found return -1
int ans = -1;
while (start <= end)
{
int mid = (start + end) / 2;
int value = C * mid;
int divC = mid - 1;
int divB = (value % B == 0) ? value / B - 1
: value / B;
int divA = (value % A == 0) ? value / A - 1
: value / A;
int divAB = (value % lcm(A, B) == 0) ?
value / lcm(A, B) - 1 :
value / lcm(A, B);
int divBC = (value % lcm(C, B) == 0) ?
value / lcm(C, B) - 1 :
value / lcm(C, B);
int divAC = (value % lcm(A, C) == 0) ?
value / lcm(A, C) - 1 :
value / lcm(A, C);
int divABC = (value % lcm(A, lcm(B, C)) == 0) ?
value / lcm(A, lcm(B, C)) - 1 :
value / lcm(A, lcm(B, C));
// Inclusion and Exclusion
int elem = divA + divB + divC - divAC -
divBC - divAB + divABC;
if (elem == (K - 1))
{
ans = value;
break;
}
// Multiple should be smaller
else if (elem > (K - 1))
{
end = mid - 1;
}
// Multiple should be bigger
else
{
start = mid + 1;
}
}
return ans;
}
// Function to return the Kth element from
// the set of multiples of A, B and C
static int findKthMultiple(int A, int B, int C, int K)
{
// Apply binary search on the multiples of A
int res = checkA(A, B, C, K);
// If the required element is not a
// multiple of A then the multiples
// of B and C need to be checked
if (res == -1)
res = checkB(A, B, C, K);
// If the required element is neither
// a multiple of A nor a multiple
// of B then the multiples of C
// need to be checked
if (res == -1)
res = checkC(A, B, C, K);
return res;
}
// Driver code
public static void main(String args[])
{
int A = 2, B = 4, C = 5, K = 5;
System.out.println(findKthMultiple(A, B, C, K));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the GCD of A and B def gcd(A, B): if (B == 0): return A return gcd(B, A % B) # Function to return the # LCM of A and B def lcm(A, B): return (A * B) // gcd(A, B) # Function to return the Kth element from # the required set if it a multiple of A def checkA(A, B, C, K): # Start and End for Binary Search start = 1 end = K # If no answer found return -1 ans = -1 while (start <= end): mid = (start + end) // 2 value = A * mid divA = mid - 1 divB = value // B - 1 if (value % B == 0) \ else value // B divC = value // C - 1 if (value % C == 0) \ else value // C divAB = value // lcm(A, B) - 1 \ if (value % lcm(A, B) == 0) \ else value // lcm(A, B) divBC = value // lcm(C, B) - 1 \ if (value % lcm(C, B) == 0) \ else value // lcm(C, B) divAC = value // lcm(A, C) - 1 \ if (value % lcm(A, C) == 0) \ else value // lcm(A, C) divABC = value // lcm(A, lcm(B, C)) - 1 \ if (value % lcm(A, lcm(B, C)) == 0) \ else value // lcm(A, lcm(B, C)) # Inclusion and Exclusion elem = divA + divB + divC - \ divAC - divBC - divAB + divABC if (elem == (K - 1)): ans = value break # Multiple should be smaller elif (elem > (K - 1)): end = mid - 1 # Multiple should be bigger else : start = mid + 1 return ans # Function to return the Kth element from # the required set if it a multiple of B def checkB(A, B, C, K): # Start and End for Binary Search start = 1 end = K # If no answer found return -1 ans = -1 while (start <= end): mid = (start + end) // 2 value = B * mid divB = mid - 1 if (value % A == 0): divA = value // A - 1 else: value // A if (value % C == 0): divC = value // C - 1 else: value // C if (value % lcm(A, B) == 0): divAB = value // lcm(A, B) -1 else: value // lcm(A, B) if (value % lcm(C, B) == 0): divBC = value // lcm(C, B) -1 else: value // lcm(C, B) if (value % lcm(A, C) == 0): divAC = value // lcm(A, C) -1 else: value // lcm(A, C) if (value % lcm(A, lcm(B, C)) == 0): divABC = value // lcm(A, lcm(B, C)) - 1 else: value // lcm(A, lcm(B, C)) # Inclusion and Exclusion elem = divA + divB + divC - \ divAC - divBC - divAB + divABC if (elem == (K - 1)): ans = value break # Multiple should be smaller elif (elem > (K - 1)): end = mid - 1 # Multiple should be bigger else : start = mid + 1 return ans # Function to return the Kth element from # the required set if it a multiple of C def checkC(A, B, C, K): # Start and End for Binary Search start = 1 end = K # If no answer found return -1 ans = -1 while (start <= end): mid = (start + end) // 2 value = C * mid divC = mid - 1 if (value % B == 0): divB = value // B - 1 else: value // B if (value % A == 0): divA = value // A - 1 else: value // A if (value % lcm(A, B) == 0): divAB = value // lcm(A, B) -1 else: value // lcm(A, B) if (value % lcm(C, B) == 0): divBC = value // lcm(C, B) -1 else: value // lcm(C, B) if (value % lcm(A, C) == 0): divAC = value // lcm(A, C) -1 else: value // lcm(A, C) if (value % lcm(A, lcm(B, C)) == 0): divABC = value // lcm(A, lcm(B, C)) - 1 else: value // lcm(A, lcm(B, C)) # Inclusion and Exclusion elem = divA + divB + divC - \ divAC - divBC - divAB + divABC if (elem == (K - 1)): ans = value break # Multiple should be smaller elif (elem > (K - 1)): end = mid - 1 # Multiple should be bigger else : start = mid + 1 return ans # Function to return the Kth element from # the set of multiples of A, B and C def findKthMultiple(A, B, C, K): # Apply binary search on the multiples of A res = checkA(A, B, C, K) # If the required element is not a # multiple of A then the multiples # of B and C need to be checked if (res == -1): res = checkB(A, B, C, K) # If the required element is neither # a multiple of A nor a multiple # of B then the multiples of C # need to be checked if (res == -1): res = checkC(A, B, C, K) return res # Driver code A = 2 B = 4 C = 5 K = 5 print(findKthMultiple(A, B, C, K)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to return the
// GCD of A and B
static int gcd(int A, int B)
{
if (B == 0)
return A;
return gcd(B, A % B);
}
// Function to return the
// LCM of A and B
static int lcm(int A, int B)
{
return (A * B) / gcd(A, B);
}
// Function to return the Kth element from
// the required set if it a multiple of A
static int checkA(int A, int B, int C, int K)
{
// Start and End for Binary Search
int start = 1;
int end = K;
// If no answer found return -1
int ans = -1;
while (start <= end)
{
int mid = (start + end) / 2;
int value = A * mid;
int divA = mid - 1;
int divB = (value % B == 0) ? value / B - 1
: value / B;
int divC = (value % C == 0) ? value / C - 1
: value / C;
int divAB = (value % lcm(A, B) == 0) ?
value / lcm(A, B) - 1 :
value / lcm(A, B);
int divBC = (value % lcm(C, B) == 0) ?
value / lcm(C, B) - 1 :
value / lcm(C, B);
int divAC = (value % lcm(A, C) == 0) ?
value / lcm(A, C) - 1 :
value / lcm(A, C);
int divABC = (value % lcm(A, lcm(B, C)) == 0) ?
value / lcm(A, lcm(B, C)) - 1 :
value / lcm(A, lcm(B, C));
// Inclusion and Exclusion
int elem = divA + divB + divC - divAC -
divBC - divAB + divABC;
if (elem == (K - 1))
{
ans = value;
break;
}
// Multiple should be smaller
else if (elem > (K - 1))
{
end = mid - 1;
}
// Multiple should be bigger
else
{
start = mid + 1;
}
}
return ans;
}
// Function to return the Kth element from
// the required set if it a multiple of B
static int checkB(int A, int B, int C, int K)
{
// Start and End for Binary Search
int start = 1;
int end = K;
// If no answer found return -1
int ans = -1;
while (start <= end)
{
int mid = (start + end) / 2;
int value = B * mid;
int divB = mid - 1;
int divA = (value % A == 0) ? value / A - 1
: value / A;
int divC = (value % C == 0) ? value / C - 1
: value / C;
int divAB = (value % lcm(A, B) == 0) ?
value / lcm(A, B) - 1 :
value / lcm(A, B);
int divBC = (value % lcm(C, B) == 0) ?
value / lcm(C, B) - 1 :
value / lcm(C, B);
int divAC = (value % lcm(A, C) == 0) ?
value / lcm(A, C) - 1 :
value / lcm(A, C);
int divABC = (value % lcm(A, lcm(B, C)) == 0) ?
value / lcm(A, lcm(B, C)) - 1 :
value / lcm(A, lcm(B, C));
// Inclusion and Exclusion
int elem = divA + divB + divC - divAC -
divBC - divAB + divABC;
if (elem == (K - 1))
{
ans = value;
break;
}
// Multiple should be smaller
else if (elem > (K - 1))
{
end = mid - 1;
}
// Multiple should be bigger
else
{
start = mid + 1;
}
}
return ans;
}
// Function to return the Kth element from
// the required set if it a multiple of C
static int checkC(int A, int B, int C, int K)
{
// Start and End for Binary Search
int start = 1;
int end = K;
// If no answer found return -1
int ans = -1;
while (start <= end)
{
int mid = (start + end) / 2;
int value = C * mid;
int divC = mid - 1;
int divB = (value % B == 0) ? value / B - 1
: value / B;
int divA = (value % A == 0) ? value / A - 1
: value / A;
int divAB = (value % lcm(A, B) == 0) ?
value / lcm(A, B) - 1 :
value / lcm(A, B);
int divBC = (value % lcm(C, B) == 0) ?
value / lcm(C, B) - 1 :
value / lcm(C, B);
int divAC = (value % lcm(A, C) == 0) ?
value / lcm(A, C) - 1 :
value / lcm(A, C);
int divABC = (value % lcm(A, lcm(B, C)) == 0) ?
value / lcm(A, lcm(B, C)) - 1 :
value / lcm(A, lcm(B, C));
// Inclusion and Exclusion
int elem = divA + divB + divC - divAC -
divBC - divAB + divABC;
if (elem == (K - 1))
{
ans = value;
break;
}
// Multiple should be smaller
else if (elem > (K - 1))
{
end = mid - 1;
}
// Multiple should be bigger
else
{
start = mid + 1;
}
}
return ans;
}
// Function to return the Kth element from
// the set of multiples of A, B and C
static int findKthMultiple(int A, int B, int C, int K)
{
// Apply binary search on the multiples of A
int res = checkA(A, B, C, K);
// If the required element is not a
// multiple of A then the multiples
// of B and C need to be checked
if (res == -1)
res = checkB(A, B, C, K);
// If the required element is neither
// a multiple of A nor a multiple
// of B then the multiples of C
// need to be checked
if (res == -1)
res = checkC(A, B, C, K);
return res;
}
// Driver code
public static void Main(String []args)
{
int A = 2, B = 4, C = 5, K = 5;
Console.WriteLine(findKthMultiple(A, B, C, K));
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// JavaScript implementation of the above approach
// Function to return the
// GCD of A and B
function gcd(A, B) {
if (B === 0) return A;
return gcd(B, A % B);
}
// Function to return the
// LCM of A and B
function lcm(A, B) {
return (A * B) / gcd(A, B);
}
// Function to return the Kth element from
// the required set if it a multiple of A
function checkA(A, B, C, K) {
// Start and End for Binary Search
var start = 1;
var end = K;
// If no answer found return -1
var ans = -1;
while (start <= end) {
var mid = parseInt((start + end) / 2);
var value = A * mid;
var divA = mid - 1;
var divB = parseInt(value % B === 0 ? value / B - 1 : value / B);
var divC = parseInt(value % C === 0 ? value / C - 1 : value / C);
var divAB = parseInt(
value % lcm(A, B) === 0 ? value / lcm(A, B) - 1 : value / lcm(A, B)
);
var divBC = parseInt(
value % lcm(C, B) === 0 ? value / lcm(C, B) - 1 : value / lcm(C, B)
);
var divAC = parseInt(
value % lcm(A, C) === 0 ? value / lcm(A, C) - 1 : value / lcm(A, C)
);
var divABC = parseInt(
value % lcm(A, lcm(B, C)) === 0
? value / lcm(A, lcm(B, C)) - 1
: value / lcm(A, lcm(B, C))
);
// Inclusion and Exclusion
var elem = divA + divB + divC - divAC - divBC - divAB + divABC;
if (elem === K - 1) {
ans = value;
break;
}
// Multiple should be smaller
else if (elem > K - 1) {
end = mid - 1;
}
// Multiple should be bigger
else {
start = mid + 1;
}
}
return ans;
}
// Function to return the Kth element from
// the required set if it a multiple of B
function checkB(A, B, C, K) {
// Start and End for Binary Search
var start = 1;
var end = K;
// If no answer found return -1
var ans = -1;
while (start <= end) {
var mid = parseInt((start + end) / 2);
var value = B * mid;
var divB = mid - 1;
var divA = parseInt(value % A === 0 ? value / A - 1 : value / A);
var divC = parseInt(value % C === 0 ? value / C - 1 : value / C);
var divAB = parseInt(
value % lcm(A, B) === 0 ? value / lcm(A, B) - 1 : value / lcm(A, B)
);
var divBC = parseInt(
value % lcm(C, B) === 0 ? value / lcm(C, B) - 1 : value / lcm(C, B)
);
var divAC = parseInt(
value % lcm(A, C) === 0 ? value / lcm(A, C) - 1 : value / lcm(A, C)
);
var divABC = parseInt(
value % lcm(A, lcm(B, C)) === 0
? value / lcm(A, lcm(B, C)) - 1
: value / lcm(A, lcm(B, C))
);
// Inclusion and Exclusion
var elem = divA + divB + divC - divAC - divBC - divAB + divABC;
if (elem === K - 1) {
ans = value;
break;
}
// Multiple should be smaller
else if (elem > K - 1) {
end = mid - 1;
}
// Multiple should be bigger
else {
start = mid + 1;
}
}
return ans;
}
// Function to return the Kth element from
// the required set if it a multiple of C
function checkC(A, B, C, K) {
// Start and End for Binary Search
var start = 1;
var end = K;
// If no answer found return -1
var ans = -1;
while (start <= end) {
var mid = parseInt((start + end) / 2);
var value = C * mid;
var divC = mid - 1;
var divB = parseInt(value % B === 0 ? value / B - 1 : value / B);
var divA = parseInt(value % A === 0 ? value / A - 1 : value / A);
var divAB = parseInt(
value % lcm(A, B) === 0 ? value / lcm(A, B) - 1 : value / lcm(A, B)
);
var divBC = parseInt(
value % lcm(C, B) === 0 ? value / lcm(C, B) - 1 : value / lcm(C, B)
);
var divAC = parseInt(
value % lcm(A, C) === 0 ? value / lcm(A, C) - 1 : value / lcm(A, C)
);
var divABC = parseInt(
value % lcm(A, lcm(B, C)) === 0
? value / lcm(A, lcm(B, C)) - 1
: value / lcm(A, lcm(B, C))
);
// Inclusion and Exclusion
var elem = divA + divB + divC - divAC - divBC - divAB + divABC;
if (elem === K - 1) {
ans = value;
break;
}
// Multiple should be smaller
else if (elem > K - 1) {
end = mid - 1;
}
// Multiple should be bigger
else {
start = mid + 1;
}
}
return ans;
}
// Function to return the Kth element from
// the set of multiples of A, B and C
function findKthMultiple(A, B, C, K) {
// Apply binary search on the multiples of A
var res = checkA(A, B, C, K);
console.log(res);
// If the required element is not a
// multiple of A then the multiples
// of B and C need to be checked
if (res === -1) res = checkB(A, B, C, K);
// If the required element is neither
// a multiple of A nor a multiple
// of B then the multiples of C
// need to be checked
if (res === -1) res = checkC(A, B, C, K);
return res;
}
// Driver code
var A = 2,
B = 4,
C = 5,
K = 5;
document.write(findKthMultiple(A, B, C, K));
// This code is contributed by rdtank.
</script>
Producción:
8
Complejidad de tiempo: O(log K * log(min(a, b))), donde a y b son parámetros de gcd
Espacio auxiliar: O(log(min(a, b)))
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA