C++程序：查找第N个可被a或b整除的数

在这个问题中，我们给出三个数字A、B和N。我们的任务是编写一个C++程序来查找第N个可被A或B整除的数。

问题描述

第N个可被A或B整除的数。我们将找到第n个数，该数可被数字A或B整除。为此，我们将计算直到第n个可被A或B整除的数。

让我们来看一个例子来理解这个问题：

输入

A = 4, B = 3, N = 5

输出

9

解释

可被3和4整除的数是：

3, 4, 6, 8, 9, 12, …

第5个数是9。

解决方案

为了找到第n个可被A或B整除的数，我们可以简单地找到可被A或B整除的数，而该序列中的第n个数就是我们的答案。

示例

在线演示

#include<iostream>
using namespace std;
int findNTerm(int N, int A, int B) {
   int count = 0;
   int num = 1;
   while( count < N){
      if(num%A == 0 || num%B == 0)
         count++;
      if(count == N)
         return num;
         num++;
   }
   return 0;
}
int main(){
   int N = 12, A = 3, B = 4;
   cout<<N<<"th term divisible by "<<A<<" or "<<B<<" is "<<findNTerm(N, A, B)<<endl;
}

输出

12th term divisible by 3 or 4 is 24

另一种解决这个问题的方法是使用二分查找来找到第N个可被A或B整除的元素。我们将使用以下公式找到第N个数：

NTerm = maxNum/A + maxNum/B - maxNum/lcm(A,B)

并根据Nterm的值，我们将检查是否需要遍历小于maxNum或大于maxNum的数字。

示例

在线演示

#include <iostream>
using namespace std;
int findLCM(int a, int b) {
   int LCM = a, i = 2;
   while(LCM % b != 0) {
      LCM = a*i;
      i++;
   }
   return LCM;
}
int findNTerm(int N, int A, int B) {
   int start = 1, end = (N*A*B), mid;
   int LCM = findLCM(A, B);

while (start < end) {
   mid = start + (end - start) / 2;
   if ( ((mid/A) + (mid/B) - (mid/LCM)) < N)
      start = mid + 1;
   else
      end = mid;
}
   return start;
}
int main() {
   int N = 12, A = 3, B = 4;
   cout<<N<<"th term divisible by "<<A<<" or "<<B<<" is "<<findNTerm(N, A, B);
}

输出

12th term divisible by 3 or 4 is 24

Ayush Gupta

更新于：2020年10月9日

619 次浏览

开启您的职业生涯

完成课程获得认证

开始学习