C++で指定された単調シーケンスの要素位置を検索します

コンセプト

与えられた整数lと単調増加シーケンスに関して-

f（m）=am + bm [log2（m）] + cm ^ 3ここで、（a =1、2、3、…）、（b =1、2、3、…）、（c =0、1、 2、3、…）ここで、[log2（m）]は、ログを2を底にして、値を切り捨てることを示しています。この結果、

m =1の場合、値は0です。

m =2-3の場合、値は1です。

m =4-7の場合、値は2です。

m =8-15の場合、値は3です。

私たちのタスクは、f（m）=lとなるように値mを決定することです。lがシーケンスに属していない場合は、0を出力する必要があります。

値は64ビットで表すことができ、a、b、cの3つの整数が100を超えないようになっていることに注意してください。

入力

a = 2, b = 1, c = 1, l = 12168587437017

出力

23001
f(23001) = 12168587437017

入力

a = 7, b = 3, c = 0, l = 119753085330

出力

1234567890

メソッド

ナイーブアプローチの使用 −与えられたa、b、cの値に関して、mのすべての値に対してf（m）の値を見つけ、それを比較します。

効率的なアプローチの使用 −二分探索を実装し、m =（min + max）/ 2を選択します。ここで、minとmaxは、mで可能な最小値と最大値として示されます。

• f（m）
• f（m）> lの場合、mをデクリメントします。
• f（m）=lの場合、mが必須の答えです。
• ここで、必要な値が見つかるか、シーケンスで不可能になるまで、上記の手順を繰り返します。

例

// C++ implementation of the approach
#include <iostream>
#include <math.h>
#define SMALL_N 1000000
#define LARGE_N 1000000000000000
using namespace std;
// Shows function to return the value of f(m) for given values of a,
b, c, m
long long func(long long a1, long long b1, long long c1, long long
m){
      long long res1 = a1 * m;
      long long logVlaue1 = floor(log2(m));
      res1 += b1 * m * logVlaue1;
      res1 += c1 * (m * m * m);
      return res1;
   }
   long long getPositionInSeries1(long long a1, long long b1,
   long long c1, long long l){
      long long start1 = 1, end1 = SMALL_N;
      // Now if c is 0, then value of m can be in order of 10^15.
      // Now if c1!=0, then m^3 value has to be in order of 10^18
      // so maximum value of m can be 10^6.
      if (c1 == 0) {
         end1 = LARGE_N;
      }
      long long ans1 = 0;
      // Now for efficient searching, implement binary search.
      while (start1 <= end1) {
         long long mid1 = (start1 + end1) / 2;
         long long val1 = func(a1, b1, c1, mid1);
         if (val1 == l) {
            ans1 = mid1;
         break;
      }
      else if (val1 > l) {
         end1 = mid1 - 1;
      }
      else {
         start1 = mid1 + 1;
      }
   }
   return ans1;
}
// Driver code
int main(){
   long long a1 = 2, b1 = 1, c1 = 1;
   long long l = 12168587437017;
   cout << getPositionInSeries1(a1, b1, c1, l)<<endl;
   long long a2 = 7, b2 = 3, c2 = 0;
   long long l1 = 119753085330;
   cout << getPositionInSeries1(a2, b2, c2, l1)<<endl;
   long long a3 = 6, b3 = 2, c3 = 1;
   long long l2 = 11975309533;
   cout << getPositionInSeries1(a3, b3, c3, l2)<<endl;
   return 0;
}

出力

23001
1234567890
0