C++でaまたはbで割り切れるN番目の項を見つけるプログラム

この問題では、A、B、およびNの3つの数値が与えられます。私たちのタスクは、C++でAまたはBで割り切れるN番目の項を見つけるプログラムを作成することです。

問題の説明

AまたはBで割り切れるN番目の項。ここでは、AまたはBで割り切れるn番目の項を見つけます。このために、AまたはBで割り切れるn番目の数まで数えます。

問題を理解するために例を見てみましょう

入力

A =4、B =3、N =5

出力

9

説明

3と4で割り切れる項は-

3、4、6、8、9、12、…

第5期は9です。

ソリューションアプローチ

AまたはBで割り切れるn番目の項を見つける。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

問題を解決する別のアプローチは、二分探索を使用して、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