在C ++中找到第N个可被a或b整除的项的程序

在本教程中，我们将讨论一个程序，以找到第n个可被a或b整除的项。

为此，我们将提供两个整数a和b。我们的任务是找到可被a或b整除的第n个项。

示例

#include <bits/stdc++.h>
using namespace std;
//返回a和b的GCD-
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;
}

输出结果

16