Khái niệm
Cho số nguyên l và dãy đơn điệu tăng:
f(m) = a*m + b*m*[log2(m)] + c*m^3 với (a = 1, 2, 3, ...), (b = 1, 2, 3, ...), (c = 0, 1, 2, 3, ...). Ở đây [log2(m)] là log cơ số 2 làm tròn xuống. Ví dụ: m=1 -> 0; m=2-3 -> 1; m=4-7 -> 2; m=8-15 -> 3.
Tìm m sao cho f(m) = l, nếu l không thuộc dãy thì in 0. Giá trị phù hợp 64-bit, a,b,c không vượt quá 100.
Đầu vào
a = 2, b = 1, c = 1, l = 12168587437017
Đầu ra
23001 f(23001) = 12168587437017
Đầu vào
a = 7, b = 3, c = 0, l = 119753085330
Đầu ra
1234567890
Phương pháp
Cách đơn giản: với a,b,c cho trước, tính f(m) cho mọi m và so sánh.
Cách hiệu quả: dùng tìm kiếm nhị phân, m = (min + max) / 2 với min, max là giá trị min/max có thể của m:
- Nếu f(m) < l thì tăng m.
- Nếu f(m) > l thì giảm m.
- Nếu f(m) = l thì m là đáp án.
- Lặp lại cho đến khi tìm thấy hoặc xác định không có trong dãy.
Ví dụ
// C++ triển khai phương pháp
#include <iostream>
#include <math.h>
#define SMALL_N 1000000
#define LARGE_N 1000000000000000
using namespace std;
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;
if (c1 == 0) end1 = LARGE_N;
long long ans1 = 0;
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;
}
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;
}
Đầu ra
23001 1234567890 0