N-е число в наборе, кратном A, B или C

Опубликовано: 5 Января, 2022

Даны четыре целых числа N , A , B и C. Задача состоит в том, чтобы вывести N- ^е число в наборе, содержащем числа, кратные A , B или C.
Примеры:

Input: A = 2, B = 3, C = 5, N = 8
Output: 10
2, 3, 4, 5, 6, 8, 9, 10, 12, 14, …
Input: A = 2, B = 3, C = 5, N = 100
Output: 136

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: начните обход с 1, пока не найдем N- ^й элемент, который делится на A , B или C.
Эффективный подход: имея число, мы можем найти количество делителей A , B или C. Теперь можно использовать двоичный поиск, чтобы найти N- ^е число, которое делится на A , B или C.
Итак, если число num, то
count = (num / A) + (num / B) + (num / C) - (num / lcm (A, B)) - (num / lcm (C, B)) - (num / lcm (A, C )) - (число / см (A, B, C))
Ниже представлена реализация описанного выше подхода:

C ++

 // C++ program to find nth term
 // divisible by a, b or c
 #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 return the count of integers
 // from the range [1, num] which are
 // divisible by either a, b or c
 long divTermCount( long a, long b, long c, long num)
 {
    // Calculate the number of terms divisible by a, b
    // and c then remove the terms which are divisible
    // by both (a, b) or (b, c) or (c, a) and then
    // add the numbers which are divisible by a, b and c
    return ((num / a) + (num / b) + (num / c)
            - (num / ((a * b) / gcd(a, b)))
            - (num / ((c * b) / gcd(c, b)))
            - (num / ((a * c) / gcd(a, c)))
            + (num / ((((a*b)/gcd(a, b))* c) / gcd(((a*b)/gcd(a, b)), c))));
 }
 // Function for binary search to find the
 // nth term divisible by a, b or c
 int findNthTerm( int a, int b, int c, long n)
 {
    // Set low to 1 and high to LONG_MAX
    long low = 1, high = LONG_MAX, mid; 
    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, c, 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()
 {
    long a = 2, b = 3, c = 5, n = 100; 
    cout << findNthTerm(a, b, c, n);
    return 0;
 }

Джава

 // Java program to find nth term
 // divisible by a, b or c
 class GFG
 {
    // Function to return
    // gcd of a and b
    static long gcd( long a, long b)
    {
        if (a == 0 )
        {
            return b;
        }
        return gcd(b % a, a);
    }
    // Function to return the count of integers
    // from the range [1, num] which are
    // divisible by either a, b or c
    static long divTermCount( long a, long b,
                             long c, long num)
    {
        // Calculate the number of terms divisible by a, b
        // and c then remove the terms which are divisible
        // by both (a, b) or (b, c) or (c, a) and then
        // add the numbers which are divisible by a, b and c
        return ((num / a) + (num / b) + (num / c) -
                (num / ((a * b) / gcd(a, b))) -
                (num / ((c * b) / gcd(c, b))) -
                (num / ((a * c) / gcd(a, c))) +
                (num / ((a * b * c) / gcd(gcd(a, b), c))));
    }
    // Function for binary search to find the
    // nth term divisible by a, b or c
    static long findNthTerm( int a, int b, int c, long n)
    {
        
        // Set low to 1 and high to LONG_MAX
        long low = 1 , high = Long.MAX_VALUE, mid; 
        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, c, 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 = 3 , c = 5 , n = 100 ; 
        System.out.println(findNthTerm(a, b, c, n));
    }
 }
 // This code is contributed by 29AjayKumar

Python3

 # Python3 program to find nth term
 # divisible by a, b or c
 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 return the count of integers
 # from the range [1, num] which are
 # divisible by either a, b or c
 def divTermCount(a, b, c, num):
    
    # Calculate the number of terms divisible by a, b
    # and c then remove the terms which are divisible
    # by both (a, b) or (b, c) or (c, a) and then
    # add the numbers which are divisible by a, b and c
    return ((num / a) + (num / b) + (num / c) -
                (num / ((a * b) / gcd(a, b))) -
                (num / ((c * b) / gcd(c, b))) -
                (num / ((a * c) / gcd(a, c))) +
                (num / ((a * b * c) / gcd(gcd(a, b), c))));
 # Function for binary search to find the
 # nth term divisible by a, b or c
 def findNthTerm(a, b, c, n): 
    # Set low to 1 and high to LONG_MAX
    low = 1 ; high = sys.maxsize; mid = 0 ; 
    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, c, mid) < n):
            low = mid + 1 ; 
        # If current term is greater than equal to
        # n then high = mid
        else :
            high = mid;
    
    return int (low);
 # Driver code
 a = 2 ; b = 3 ; c = 5 ; n = 100 ;
 print (findNthTerm(a, b, c, n));
 # This code is contributed by 29AjayKumar

C #

 // C# program to find nth term
 // divisible by a, b or c
 using System;
 class GFG
 {
    // Function to return
    // gcd of a and b
    static long gcd( long a, long b)
    {
        if (a == 0)
        {
            return b;
        }
        return gcd(b % a, a);
    }
    // Function to return the count of integers
    // from the range [1, num] which are
    // divisible by either a, b or c
    static long divTermCount( long a, long b,
                             long c, long num)
    {
        // Calculate the number of terms divisible by a, b
        // and c then remove the terms which are divisible
        // by both (a, b) or (b, c) or (c, a) and then
        // add the numbers which are divisible by a, b and c
        return ((num / a) + (num / b) + (num / c) -
                (num / ((a * b) / gcd(a, b))) -
                (num / ((c * b) / gcd(c, b))) -
                (num / ((a * c) / gcd(a, c))) +
                (num / ((a * b * c) / gcd(gcd(a, b), c))));
    }
    // Function for binary search to find the
    // nth term divisible by a, b or c
    static long findNthTerm( int a, int b,
                            int c, long n)
    {
        
        // Set low to 1 and high to LONG_MAX
        long low = 1, high = long .MaxValue, mid; 
        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, c, 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 = 3, c = 5, n = 100; 
        Console.WriteLine(findNthTerm(a, b, c, n));
    }
 }
 // This code is contributed by PrinciRaj1992

Javascript

 <script>
 // Javascript program to find nth term
 // divisible by a, b or c
 // Function to return
 // gcd of a and b
 function gcd( a, b)
 {
    if (a == 0)
        return b; 
    return gcd(b % a, a);
 }
 // Function to return the count of integers
 // from the range [1, num] which are
 // divisible by either a, b or c
 function divTermCount( a, b, c, num)
 {
    // Calculate the number of terms divisible by a, b
    // and c then remove the terms which are divisible
    // by both (a, b) or (b, c) or (c, a) and then
    // add the numbers which are divisible by a, b and c
    return parseInt(((num / a) + (num / b) + (num / c)
            - (num / ((a * b) / gcd(a, b)))
            - (num / ((c * b) / gcd(c, b)))
            - (num / ((a * c) / gcd(a, c)))
            + (num / ((((a*b)/gcd(a, b))* c)/
            gcd(((a*b)/gcd(a, b)), c)))));
 }
 // Function for binary search to find the
 // nth term divisible by a, b or c
 function findNthTerm( a, b, c, n)
 {
    // Set low to 1 and high to LONG_MAX
     var low = 1, high = Number.MAX_SAFE_INTEGER , mid; 
    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, c, mid) < n)
            low = mid + 1;
        // If current term is greater than equal to
        // n then high = mid
        else
            high = mid;
    }
    return low;
 }
 var a = 2, b = 3, c = 5, n = 100;
 document.write(parseInt(findNthTerm(a, b, c, n)));
 // This code is contributed by SoumikMondal
 </script>

Выход:

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Technical Scripter

N-е число в наборе, кратном A, B или C

C ++

Джава

Python3

C #

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ