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