UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214862#2733. 8.4t3nodgd1002ms1192kbC++11762b2024-11-22 21:04:202024-11-22 23:13:48

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long i64;

int T, n;
i64 N, f[100];

int main() {
    f[1] = 1, f[2] = 2;
    for (n = 3; ; n ++) {
        f[n] = f[n - 1] + f[n - 2];
        if (f[n] > 1e18) break;
    }
    for (scanf("%d", &T); T --; ) {
        scanf("%lld", &N);
        i64 a0 = 1, a1 = 0, b0, b1;
        for (int i = n, j = -1; i >= 0; i --) {
            if (N < f[i]) continue;
            N -= f[i];
            if (j != -1) {
                int d = j - i;
                b0 = a0 * (d + 1 >> 1) + a1 * (d - 1 >> 1);
                b1 = ~d & 1 ? a0 + a1 : 0;
                a0 = b0, a1 = b1;
            }
            j = i;
        }
        printf("%lld\n", a0);
    }
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1192kb

input:

1000
571
1996
864
740
2193
2186
1327
1298
1473
1164
615
867
1434
2176
442
1533
813
1090
847
1392
954...

output:

18
22
20
7
8
24
22
20
6
5
11
25
16
34
13
11
10
24
9
12
12
10
9
8
21
17
18
24
14
10
3
27
12
10
3
26
2...

result:

ok 1000 numbers

Test #2:

score: 10
Accepted
time: 0ms
memory: 1188kb

input:

1000
3356
1171
136
1062
3011
1035
572
3025
1649
2608
912
2332
2317
3454
1638
1219
2158
2577
3029
158...

output:

36
25
7
7
48
20
9
34
17
28
18
19
32
40
9
2
30
13
39
17
27
2
4
16
32
6
20
36
20
20
38
16
15
18
40
14
...

result:

ok 1000 numbers

Test #3:

score: 10
Accepted
time: 0ms
memory: 1192kb

input:

1000
2050
378
4960
4668
2948
1963
2018
292
2678
2495
101
2950
4914
1251
2319
3253
1537
4206
676
2037...

output:

34
6
25
48
36
18
24
6
28
20
3
24
44
18
24
18
26
12
21
42
7
40
32
37
51
32
14
24
11
24
23
35
14
21
40...

result:

ok 1000 numbers

Test #4:

score: 10
Accepted
time: 0ms
memory: 1188kb

input:

1000
104219
800
26539
61330
5714
5364
31307
19569
81083
92568
123288
53335
80239
107835
102985
2248
...

output:

180
8
60
132
22
40
96
48
169
88
125
147
56
110
96
12
35
96
210
61
160
65
63
36
49
180
39
18
120
90
6...

result:

ok 1000 numbers

Test #5:

score: 10
Accepted
time: 0ms
memory: 1188kb

input:

1000
157832
190060
170249
203038
145928
276268
181737
444496
14683
311941
19456
60574
361256
209132
...

output:

144
120
182
17
76
257
234
294
68
146
36
168
216
290
147
51
275
95
84
204
144
85
100
67
140
287
384
2...

result:

ok 1000 numbers

Test #6:

score: 10
Accepted
time: 1ms
memory: 1188kb

input:

1000
14080208
88545879
19525576
73869550
29790859
35683476
34070290
55040452
41239264
80671558
34083...

output:

819
2968
448
3654
330
900
2172
1870
2020
1520
2160
495
4446
1891
1512
1008
450
2058
1170
1260
4032
1...

result:

ok 1000 numbers

Test #7:

score: 10
Accepted
time: 0ms
memory: 1188kb

input:

1000
440550064
431992015
780562848
560891500
136906959
874374877
803701364
912120737
617697408
81277...

output:

1320
2988
3666
2704
7200
13312
2313
6816
4160
4095
6336
3642
9261
4608
3780
1050
11616
2520
2478
598...

result:

ok 1000 numbers

Test #8:

score: 10
Accepted
time: 0ms
memory: 1188kb

input:

1000
384997060794894
3052576495984458
2515613738333319
2758137799841781
2771826157513722
25973702479...

output:

3139200
10701054
2979840
6652800
4221360
3611520
19392120
9441120
3250368
7143552
4781028
10160640
9...

result:

ok 1000 numbers

Test #9:

score: 10
Accepted
time: 1ms
memory: 1192kb

input:

1000
438790986257646999
739257800188095523
841238673343474427
320309202621474808
554464838878161478
...

output:

17273088
34100352
20988000
17424000
41233536
68006400
81899520
46305000
12067380
42797700
68610564
4...

result:

ok 1000 numbers

Test #10:

score: 10
Accepted
time: 0ms
memory: 1192kb

input:

30
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

output:

1
1
2
1
2
2
1
3
2
2
3
1
3
3
2
4
2
3
3
1
4
3
3
5
2
4
4
2
5
3

result:

ok 30 numbers