ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214862 | #2733. 8.4t3 | nodgd | 100 | 2ms | 1192kb | C++11 | 762b | 2024-11-22 21:04:20 | 2024-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