（（n％i）％j）％nがC++で最大化されるような（i、j）のペアの数

入力として数値numが与えられます。目標は、（（num％i）％j）％numが最大化され、iとjの両方が[1、num]の範囲内にあるような形式（i、j）のペアの数を見つけることです。

例を挙げて理解しましょう

入力 − num =4

出力 −（（n％i）％j）％nが最大になるような（i、j）のペアの数は− 3

説明 −ペアは次のようになります：（3,2）、（3,3）、（3,4）

入力 − num =6

出力 −（（n％i）％j）％nが最大になるような（i、j）のペアの数は− 4

説明 −ペアは次のようになります：（4,3、（4,4）、（4,5）、（4,6）

以下のプログラムで使用されているアプローチは次のとおりです

この問題は、2つのアプローチを使用して解決します。ナイーブなアプローチでは、numを半分にすると、最大の剰余値を取得できます。 temp =num /2+1を設定します。最大余りをtotal=num％tempとして設定します。 i、jを0からnumまでトラバースし、（（num％i）％j）％num ==totalとなるようなi、jを見つけます。

• 入力数値を整数とします。

• 関数maximized_pa​​ir（int num）はnumを取り、（（n％i）％j）％nが最大化されるように（i、j）のペアの数を返します。

• 初期カウントを0とします。

• 余りを最大にするには、numを半分に減らします。 temp =（（num / 2）+ 1）を設定します。

• 最大余りを合計として計算=num％temp;

• ペア（i、j）の場合。 [1、num]の範囲のiとjの2つのforループを使用してトラバースします。

• 値（（num％i）％j）％numがtotalに等しい場合は、カウントをインクリメントします。

• 両方のforループの最後に、結果としてカウントが返されます。

効率的なアプローチ

合計としての最大余り=num％temp ここで、tempはnum/ 2 + 1 。ここで、ペア（i、j）の場合、最大の余りを取得するには、numとしてiを選択する必要があります。合計を最大にするために、合計からnumまでの範囲からjを選択できます。したがって、ペアの数は num-totalになります 。

num=2の場合 、ペアが（1,1）、（1,2）、（2,1）、（2,2）になり、num-totalを使用して計算されないため、4を返します。

• 入力数値を整数とします。

• 関数maximized_pa​​ir（int num）はnumを取り、（（n％i）％j）％nが最大化されるように（i、j）のペアの数を返します。

• 初期カウントを0とします。

• num ==2の場合、4を返します。

• それ以外の場合は、numを半分に減らして残りを最大にします。 temp =（（num / 2）+ 1）を設定します。

• 最大余りを合計として計算=num％temp;

• count =num-total

  を設定します

• 結果として最後にリターンカウント。

例（素朴なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int maximized_pair(int num){
   int count = 0;
   int temp = ((num / 2) + 1);
   int total = num % temp;
   for (int i = 1; i <= num; i++){
      for (int j = 1; j <= num; j++){
         int check = ((num % i) % j) % num;
         if (check == total){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int num = 10;
   cout<<"Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: "<<maximized_pair(num);
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: 6

例（効率的なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int maximized_pair(int num){
   int count = 0;
   if (num == 2){
      return 4;
   }
   else{
      int temp = ((num / 2) + 1);
      int total = num % temp;
      count = num - total;
   }
   return count;
}
int main(){
   int num = 10;
   cout<<"Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: "<<maximized_pair(num);
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: 6