解題區/解題區 - UVa

UVa 13036 - Birthday Gift to SJ - 2

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

問在區間 $[a, b]$ 之中最大的 interesting number，所謂的 interesting number 就是分解成數個費波納契數的乘積。

Sample Input

1
2
3
4
3
1  7
1  10
1  1000000000000000000

Sample Output

1
2
3
6
10
1000000000000000000

Solution

由於費波納契數成長速度非常快，用不著擔心會有好幾種不同數構成，因此可以採用中間相遇法，將前幾個小的費波納契數任意組合，後半則是剩餘的組合。至於要從哪裡開始拆團，必須手動測一下。

而這一題詢問次數非常多，儘管建好表，$\mathcal{O}(N \log N)$ 的搜索相當慢，甚至會 TLE，最好使用一次二分搜尋，或者利用單調性質降到 $\mathcal{O}(N)$ 以下最為保險。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
// Algorithm: Meet in Middle
const int MAXN = 85;
const long long MAXV = 1e+18;
long long F[100] = {2, 3};
vector<long long> S1, S2;
void bfs(int begin, int end, vector<long long> &S) {
    S.push_back(1);
    for (int i = begin; i < end; i++) {
        long long x = F[i];
        vector<long long> next(S);
        for (auto e : S) {
            while (MAXV / e / x) {
                e *= x;
                next.push_back(e);
            }
        }
        S = next;
    }
    sort(S.begin(), S.end());
  	S.resize(unique(S.begin(), S.end()) - S.begin());
}
int main() {
    for (int i = 2; i < MAXN; i++) {
        F[i] = F[i-1] + F[i-2];
        assert(F[i] / MAXV == 0);
    }
    int split = 9;
    bfs(0, split, S1);
    bfs(split, MAXN, S2);
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        long long a, b;
        long long ret = -1;
        scanf("%lld %lld", &a, &b);
        int idx1 = 0, idx2 = S2.size()-1;
        for (; idx1 < S1.size(); idx1++) {
            if (S1[idx1] > b)	break;
            long long e = S1[idx1];
            while (idx2 > 0 && b / S2[idx2] / e == 0)
                idx2--;
            long long t = S2[idx2] * e;
            if (t >= a)
                ret = max(ret, t);
        }
        vector<long long>::iterator it = lower_bound(S1.begin(), S1.end(), b);
        if (it == S1.end() || it != S1.begin() && *it > b)	it--;
        if (it != S1.end() && b / *it) {
            long long t = *it;
            if (t >= a)
                ret = max(ret, t);
        }
        it = lower_bound(S2.begin(), S2.end(), b);
        if (it == S2.end() || it != S2.begin() && *it > b)	it--;
        if (it != S2.end() && b / *it) {
            long long t = *it;
            if (t >= a)
                ret = max(ret, t);
        }
        printf("%lld\n", ret);
    }
    return 0;
}
/*
1
5231711 13073137
*/