寻找ABCDEF

1.1k 词

题目描述

寻找6个数ABCDEF,满足$1<=A<=B<=C<=D<=E<=F<=100$ 且 $A^5+B^5+C^5+D^5+E^5=F^5$

输出所有的解

输出

$A B C D E F $用空格分割

题解

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
#include <iostream>

using namespace std;
#define endl '\n'
using ll = long long;
const int N = 100;

ll h(int x) {
return 1ll * x * x * x * x * x;
}

ll H[N + 1];

void Fill() {
for (int i = 0; i <= N; ++i) H[i] = h(i);
}//中括号提速八倍
int cmp(const void *a, const void *b) {
ll *la = (ll *) a;
ll *lb = (ll *) b;
ll d = *la - *lb;
if (d < 0)return -1;
if (d > 0)return 1;
return 0;
}

//5.空间换时间 用改进的二分查找代替循环 改进枚举法顺序
void step5() {
Fill();
for (int e = 1; e <= N; e++)
for (int d = 1; d <= e; d++)
for (int c = 1; c <= d; c++)
for (int b = 1; b <= c; b++)
for (int a = 1; a <= b; a++) {
ll key = H[a] + H[b] + H[c] + H[d] + H[e];
ll *pos = (ll *) bsearch(&key, H + e + 1, N - e, sizeof(H[0]), cmp);
if (pos)
cout << a << " " << b << " " << c << " " << d << " " << e << " " << pos - H << endl;
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
step5();
return 0;
}