IMO 2021 第 1 题拓展问题的两个极值的编程求解
2021/8/8 11:06:34
本文主要是介绍IMO 2021 第 1 题拓展问题的两个极值的编程求解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
IMO 2021 第 1 题拓展问题的两个极值的编程求解
本篇是 IMO 2021 第一题题解及相关拓展问题分析 的续篇。
拓展问题三：
(I). 求 n 的最小值，使得 n, n + 1, ..., 2n 中存在奇数环；
(II). 求 k 的最小值，使得当 n ≥ k 时，n, n + 1, ..., 2n 中存在奇数环。
SItem 结构定义
1 #include <stdio.h>
2 #include <stdint.h>
3 #include <string>
4 #include <list>
5 #include <set>
6 #include <map>
7 #include <iostream>
8
9 typedef unsigned char u8;
10 struct SItem
11 {
12 int num;
13 u8 grp;
14 std::set<int> squares;
15
16 SItem() {}
17 SItem(int val, u8 group, int square) {
18 num = val; grp = group;
19 if (square != 0)
20 squares.insert(square);
21 }
22 };
check 函数实现
1 bool check(int val)
2 {
3 int head = val;
4 int tail = val + val;
5 int hsum = tail + 1;
6 int tsum = tail + tail - 1;
7 std::map<int, int> mapSquare;
8 int idx = 2;
9 int square = idx * idx;
10 printf("For n=%d, square set:", head);
11 while (square <= tsum) {
12 if (square >= hsum) {
13 mapSquare[idx] = square;
14 printf(" %d", square);
15 }
16 ++idx;
17 square = idx * idx;
18 }
19 printf(".\n");
20 if (mapSquare.size() <= 2)
21 return true;
22 size_t squares = mapSquare.size();
23 std::map<int, int>::iterator itS = mapSquare.begin();
24 for (; squares >= 3; --squares, ++itS) {
25 if (itS->first % 2 == 1) {
26 int k = (itS->first + 1) / 2;
27 int a = k * 2 * (k - 2), b = k * k * 2 + 1, c = k * 2 * (k + 2);
28 if (a >= head && c <= tail) {
29 printf("a=%d, b=%d, c=%d.\n", a, b, c);
30 return false;
31 }
32 }
33 }
34 /// grouping
35 idx = head;
36 std::map<int, SItem> mapDone;
37 std::list<SItem> lstPending;
38 bool bFlict = false;
39 while (idx <= tail) {
40 if (lstPending.empty()) {
41 if (mapDone.find(idx) != mapDone.end()) {
42 ++idx;
43 continue;
44 }
45 SItem item(idx, 0, 0);
46 lstPending.push_back(item);
47 }
48 std::list<SItem>::iterator itHead = lstPending.begin();
49 for (auto it = mapSquare.begin(); it != mapSquare.end(); ++it) {
50 if (itHead->squares.find(it->second) != itHead->squares.end())
51 continue;
52 int oppo = it->second - itHead->num;
53 if (oppo == itHead->num)
54 continue;
55 if (oppo < head || oppo > tail)
56 continue;
57 std::map<int, SItem>::iterator itM = mapDone.find(oppo);
58 if (itM != mapDone.end()) {
59 if (itM->second.grp == 1 - itHead->grp)
60 continue;
61 printf("n=%d: %d must belong to both groups when dealing %d!\n", head, oppo, itHead->num);
62 bFlict = true;
63 break;
64 }
65 SItem item(oppo, 1 - itHead->grp, it->second);
66 lstPending.push_back(item);
67 itHead->squares.insert(it->second);
68 } // end of inner loop
69 if (bFlict) {
70 break;
71 }
72 mapDone[itHead->num] = *itHead;
73 lstPending.erase(itHead);
74 } // end of outer loop
75 printf("Grouping info for n=%d:\n", head);
76 for (auto it = mapDone.begin(); it != mapDone.end(); ++it)
77 printf(" %d[%d]", it->first, (int)it->second.grp);
78 printf(".\n");
79 if (!lstPending.empty()) {
80 printf("Pending info:\n");
81 for (auto it = lstPending.begin(); it != lstPending.end(); ++it)
82 printf(" %d[%d]", it->num, (int)it->grp);
83 printf(".\n");
84 }
85 return (!bFlict);
86 }
main 函数实现
1 int main()
2 {
3 printf("The 1st number please: ");
4 std::string strInput;
5 getline(std::cin, strInput);
6 int raw = (int)strtoul(strInput.c_str(), 0, 10);
7 if (raw >= 100 || raw < 3) {
8 printf("\n The 1st number should be in [3,99].\n");
9 getline(std::cin, strInput);
10 return 0;
11 }
12 std::list<int> lstCan;
13 std::list<int> lstNot;
14 for (int idx = raw; idx < raw + 15 && idx <= 100; ++idx)
15 if (check(idx))
16 lstCan.push_back(idx);
17 else
18 lstNot.push_back(idx);
19 printf("\n");
20 if (!lstCan.empty()) {
21 printf("CAN-list:");
22 for (auto it = lstCan.begin(); it != lstCan.end(); ++it)
23 printf(" %d", *it);
24 printf(".\n");
25 }
26 if (!lstNot.empty()) {
27 printf("NOT-list:");
28 for (auto it = lstNot.begin(); it != lstNot.end(); ++it)
29 printf(" %d", *it);
30 printf(".\n");
31 }
32 getline(std::cin, strInput);
33 return 0;
34 }
n = 3 到 17 的运行结果分析
PS H:\Read\num\Release> .\grouping The 1st number please: 3 For n=3, square set: 9. For n=4, square set: 9. For n=5, square set: 16. For n=6, square set: 16. For n=7, square set: 16 25. For n=8, square set: 25. For n=9, square set: 25. For n=10, square set: 25 36. For n=11, square set: 25 36. For n=12, square set: 25 36. For n=13, square set: 36 49. For n=14, square set: 36 49. For n=15, square set: 36 49. For n=16, square set: 36 49. For n=17, square set: 36 49 64. Grouping info for n=17: 17[0] 18[0] 19[1] 20[0] 21[0] 22[0] 23[0] 24[0] 25[1] 26[1] 27[1] 28[1] 29[1] 30[0] 31[1] 32[1] 33[0] 34[1]. CAN-list: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17.
n = 3 时，n, n+1, ..., 2n 中两数之和只有一个完全平方数，即 9，由前面分析，n, n+1, ..., 2n 可以分为两组，使得其中每组中两数之和均不是完全平方数。n = 4, ..., 16 时，有同样结论。
n = 17 时，n, n+1, ..., 2n 中两数之和有 3 个完全平方数，即 36, 49, 64，但 n, n+1, ..., 2n 还是可以分为两组，使得其中每组中两数之和均不是完全平方数，程序运行结果具体给出了一种分组方法，其中 [0] 表示 A 组，[1] 表示 B 组，如 17[0] 表示 17 在 A 组。
n = 3, 4, ..., 17 都是可分的情形（n, n+1, ..., 2n 可以分为两组，使得其中每组中两数之和均不是完全平方数），故有 CAN-list: 3 4 ... 17.
n = 18 到 32 的运行结果分析
PS H:\Read\num\Release> .\grouping The 1st number please: 18 For n=18, square set: 49 64. For n=19, square set: 49 64. For n=20, square set: 49 64. For n=21, square set: 49 64 81. Grouping info for n=21: 21[0] 22[0] 23[1] 24[0] 25[1] 26[0] 27[1] 28[1] 29[0] 30[0] 31[0] 32[0] 33[1] 34[1] 35[1] 36[0] 37[0] 38[1] 39[0] 40[1] 41[0] 42[1]. For n=22, square set: 49 64 81. Grouping info for n=22: 22[0] 23[1] 24[0] 25[1] 26[0] 27[1] 28[0] 29[0] 30[0] 31[0] 32[0] 33[1] 34[1] 35[1] 36[1] 37[0] 38[1] 39[0] 40[1] 41[0] 42[1] 43[0] 44[1]. For n=23, square set: 49 64 81. Grouping info for n=23: 23[0] 24[1] 25[0] 26[1] 27[0] 28[0] 29[0] 30[0] 31[0] 32[0] 33[1] 34[1] 35[1] 36[1] 37[1] 38[0] 39[1] 40[0] 41[1] 42[0] 43[1] 44[0] 45[0] 46[0]. For n=24, square set: 49 64 81. Grouping info for n=24: 24[0] 25[1] 26[0] 27[0] 28[0] 29[0] 30[0] 31[0] 32[0] 33[1] 34[1] 35[1] 36[1] 37[1] 38[1] 39[0] 40[1] 41[0] 42[1] 43[0] 44[0] 45[0] 46[0] 47[0] 48[0]. For n=25, square set: 64 81. For n=26, square set: 64 81 100. Grouping info for n=26: 26[0] 27[0] 28[0] 29[0] 30[0] 31[0] 32[1] 33[1] 34[1] 35[1] 36[1] 37[1] 38[1] 39[0] 40[0] 41[1] 42[1] 43[0] 44[0] 45[0] 46[0] 47[0] 48[0] 49[0] 50[1] 51[1] 52[1]. For n=27, square set: 64 81 100. Grouping info for n=27: 27[0] 28[0] 29[0] 30[0] 31[0] 32[1] 33[1] 34[1] 35[1] 36[1] 37[1] 38[0] 39[0] 40[0] 41[1] 42[1] 43[1] 44[0] 45[0] 46[0] 47[0] 48[0] 49[0] 50[1] 51[1] 52[1] 53[1] 54[1]. For n=28, square set: 64 81 100. Grouping info for n=28: 28[0] 29[0] 30[0] 31[0] 32[1] 33[1] 34[1] 35[1] 36[1] 37[0] 38[0] 39[0] 40[0] 41[1] 42[1] 43[1] 44[1] 45[0] 46[0] 47[0] 48[0] 49[0] 50[1] 51[1] 52[1] 53[1] 54[1] 55[1] 56[0]. For n=29, square set: 64 81 100. Grouping info for n=29: 29[0] 30[0] 31[0] 32[1] 33[1] 34[1] 35[1] 36[0] 37[0] 38[0] 39[0] 40[0] 41[1] 42[1] 43[1] 44[1] 45[1] 46[0] 47[0] 48[0] 49[0] 50[1] 51[1] 52[1] 53[1] 54[1] 55[0] 56[0] 57[0] 58[0]. For n=30, square set: 64 81 100. Grouping info for n=30: 30[0] 31[0] 32[1] 33[1] 34[1] 35[0] 36[0] 37[0] 38[0] 39[0] 40[0] 41[1] 42[1] 43[1] 44[1] 45[1] 46[1] 47[0] 48[0] 49[0] 50[1] 51[1] 52[1] 53[1] 54[0] 55[0] 56[0] 57[0] 58[0] 59[0] 60[1]. For n=31, square set: 64 81 100 121. Grouping info for n=31: 31[0] 32[0] 33[1] 34[0] 35[0] 36[0] 37[0] 38[0] 39[1] 40[0] 41[1] 42[0] 43[1] 44[1] 45[1] 46[1] 47[1] 48[0] 49[1] 50[1] 51[0] 52[1] 53[0] 54[0] 55[0] 56[0] 57[0] 58[1] 59[0] 60[1] 61[0] 62[1]. For n=32, square set: 81 100 121. Grouping info for n=32: 32[0] 33[0] 34[0] 35[0] 36[0] 37[1] 38[0] 39[1] 40[0] 41[1] 42[0] 43[1] 44[0] 45[1] 46[1] 47[1] 48[1] 49[1] 50[0] 51[0] 52[0] 53[0] 54[0] 55[0] 56[1] 57[0] 58[1] 59[0] 60[1] 61[0] 62[1] 63[0] 64[1]. CAN-list: 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32.
n = 18, 19, ..., 32 都是可分的情形。
n = 33 到 47 的运行结果分析
PS H:\Read\num\Release> .\grouping The 1st number please: 33 For n=33, square set: 81 100 121. Grouping info for n=33: 33[0] 34[0] 35[1] 36[0] 37[1] 38[0] 39[1] 40[0] 41[1] 42[0] 43[1] 44[0] 45[1] 46[0] 47[1] 48[1] 49[0] 50[0] 51[1] 52[0] 53[0] 54[1] 55[0] 56[1] 57[0] 58[1] 59[0] 60[1] 61[0] 62[1] 63[0] 64[1] 65[0] 66[1]. For n=34, square set: 81 100 121. Grouping info for n=34: 34[0] 35[1] 36[0] 37[1] 38[0] 39[1] 40[0] 41[1] 42[0] 43[1] 44[0] 45[1] 46[0] 47[1] 48[0] 49[0] 50[0] 51[1] 52[1] 53[0] 54[1] 55[0] 56[1] 57[0] 58[1] 59[0] 60[1] 61[0] 62[1] 63[0] 64[1] 65[0] 66[1] 67[0] 68[1]. For n=35, square set: 81 100 121. Grouping info for n=35: 35[0] 36[1] 37[0] 38[1] 39[0] 40[1] 41[0] 42[1] 43[0] 44[1] 45[0] 46[1] 47[0] 48[0] 49[0] 50[0] 51[1] 52[1] 53[1] 54[0] 55[1] 56[0] 57[1] 58[0] 59[1] 60[0] 61[1] 62[0] 63[1] 64[0] 65[1] 66[0] 67[1] 68[0] 69[0] 70[0]. For n=36, square set: 81 100 121. Grouping info for n=36: 36[0] 37[1] 38[0] 39[1] 40[0] 41[1] 42[0] 43[1] 44[0] 45[1] 46[0] 47[0] 48[0] 49[0] 50[0] 51[1] 52[1] 53[1] 54[1] 55[0] 56[1] 57[0] 58[1] 59[0] 60[1] 61[0] 62[1] 63[0] 64[1] 65[0] 66[1] 67[0] 68[0] 69[0] 70[0] 71[1] 72[1]. For n=37, square set: 81 100 121 144. Grouping info for n=37: 37[0] 38[1] 39[0] 40[1] 41[0] 42[1] 43[0] 44[1] 45[0] 46[0] 47[0] 48[0] 49[0] 50[1] 51[1] 52[1] 53[1] 54[1] 55[1] 56[0] 57[1] 58[0] 59[1] 60[0] 61[1] 62[0] 63[1] 64[0] 65[1] 66[0] 67[0] 68[0] 69[0] 70[0] 71[0] 72[1] 73[1] 74[1]. For n=38, square set: 81 100 121 144. Grouping info for n=38: 38[0] 39[1] 40[0] 41[1] 42[0] 43[1] 44[0] 45[0] 46[0] 47[0] 48[0] 49[0] 50[1] 51[1] 52[1] 53[1] 54[1] 55[1] 56[1] 57[0] 58[1] 59[0] 60[1] 61[0] 62[1] 63[0] 64[1] 65[0] 66[0] 67[0] 68[0] 69[0] 70[0] 71[0] 72[1] 73[1] 74[1] 75[1] 76[1]. For n=39, square set: 81 100 121 144. Grouping info for n=39: 39[0] 40[1] 41[0] 42[1] 43[0] 44[0] 45[0] 46[0] 47[0] 48[0] 49[0] 50[1] 51[1] 52[1] 53[1] 54[1] 55[1] 56[1] 57[1] 58[0] 59[1] 60[0] 61[1] 62[0] 63[1] 64[0] 65[0] 66[0] 67[0] 68[0] 69[0] 70[0] 71[0] 72[1] 73[1] 74[1] 75[1] 76[1] 77[1] 78[1]. For n=40, square set: 81 100 121 144. Grouping info for n=40: 40[0] 41[1] 42[0] 43[1] 44[0] 45[1] 46[0] 47[1] 48[0] 49[1] 50[1] 51[0] 52[1] 53[0] 54[1] 55[0] 56[1] 57[0] 58[1] 59[0] 60[1] 61[0] 62[1] 63[0] 64[1] 65[0] 66[1] 67[0] 68[1] 69[0] 70[1] 71[0] 72[0] 73[1] 74[0] 75[1] 76[0] 77[1] 78[0] 79[1] 80[0]. For n=41, square set: 100 121 144. Grouping info for n=41: 41[0] 42[0] 43[0] 44[0] 45[0] 46[0] 47[0] 48[0] 49[0] 50[1] 51[1] 52[1] 53[1] 54[1] 55[1] 56[1] 57[1] 58[1] 59[1] 60[0] 61[1] 62[0] 63[0] 64[0] 65[0] 66[0] 67[0] 68[0] 69[0] 70[0] 71[0] 72[1] 73[1] 74[1] 75[1] 76[1] 77[1] 78[1] 79[1] 80[1] 81[1] 82[1]. For n=42, square set: 100 121 144. Grouping info for n=42: 42[0] 43[0] 44[0] 45[0] 46[0] 47[0] 48[0] 49[0] 50[1] 51[1] 52[1] 53[1] 54[1] 55[1] 56[1] 57[1] 58[1] 59[0] 60[0] 61[1] 62[1] 63[0] 64[0] 65[0] 66[0] 67[0] 68[0] 69[0] 70[0] 71[0] 72[1] 73[1] 74[1] 75[1] 76[1] 77[1] 78[1] 79[1] 80[1] 81[1] 82[0] 83[0] 84[1]. For n=43, square set: 100 121 144 169. Grouping info for n=43: 43[0] 44[0] 45[0] 46[0] 47[0] 48[0] 49[0] 50[1] 51[1] 52[1] 53[1] 54[1] 55[1] 56[1] 57[1] 58[0] 59[1] 60[0] 61[1] 62[0] 63[1] 64[0] 65[0] 66[0] 67[0] 68[0] 69[0] 70[0] 71[0] 72[1] 73[1] 74[1] 75[1] 76[1] 77[1] 78[1] 79[1] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1]. For n=44, square set: 100 121 144 169. Grouping info for n=44: 44[0] 45[0] 46[0] 47[0] 48[0] 49[0] 50[1] 51[1] 52[1] 53[1] 54[1] 55[1] 56[1] 57[0] 58[1] 59[0] 60[1] 61[0] 62[1] 63[0] 64[1] 65[0] 66[0] 67[0] 68[0] 69[0] 70[0] 71[0] 72[1] 73[1] 74[1] 75[1] 76[1] 77[1] 78[1] 79[1] 80[0] 81[1] 82[0] 83[1] 84[0] 85[1] 86[0] 87[1] 88[0]. For n=45, square set: 100 121 144 169. Grouping info for n=45: 45[0] 46[1] 47[0] 48[1] 49[0] 50[0] 51[1] 52[0] 53[1] 54[0] 55[1] 56[0] 57[1] 58[0] 59[1] 60[0] 61[1] 62[0] 63[1] 64[0] 65[1] 66[0] 67[1] 68[0] 69[1] 70[0] 71[1] 72[1] 73[0] 74[1] 75[0] 76[1] 77[0] 78[1] 79[0] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1] 87[0] 88[1] 89[0] 90[1]. For n=46, square set: 100 121 144 169. Grouping info for n=46: 46[0] 47[1] 48[0] 49[1] 50[1] 51[0] 52[1] 53[0] 54[1] 55[0] 56[1] 57[0] 58[1] 59[0] 60[1] 61[0] 62[1] 63[0] 64[1] 65[0] 66[1] 67[0] 68[1] 69[0] 70[1] 71[0] 72[0] 73[1] 74[0] 75[1] 76[0] 77[1] 78[0] 79[1] 80[0] 81[1] 82[0] 83[1] 84[0] 85[1] 86[0] 87[1] 88[0] 89[1] 90[0] 91[1] 92[0]. For n=47, square set: 100 121 144 169. Grouping info for n=47: 47[0] 48[1] 49[0] 50[0] 51[1] 52[0] 53[1] 54[0] 55[1] 56[0] 57[1] 58[0] 59[1] 60[0] 61[1] 62[0] 63[1] 64[0] 65[1] 66[0] 67[1] 68[0] 69[1] 70[0] 71[1] 72[1] 73[0] 74[1] 75[0] 76[1] 77[0] 78[1] 79[0] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1] 87[0] 88[1] 89[0] 90[1] 91[0] 92[1] 93[0] 94[1]. CAN-list: 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47.
同样，n = 32, 33, ..., 47 都是可分的情形。
至此，拓展 3 的第 1 个问题的求解可知为 n = 48。
n = 48 到 62 的运行结果分析
PS H:\Read\num\Release> .\grouping The 1st number please: 48 For n=48, square set: 100 121 144 169. a=48, b=73, c=96. For n=49, square set: 100 121 144 169. n=49: 70 must belong to both groups when dealing 74! Grouping info for n=49: 49[0] 51[1] 70[0] 72[1] 93[0] 95[1] 97[0]. Pending info: 74[0] 74[1] 76[1]. For n=50, square set: 121 144 169 196. Grouping info for n=50: 50[0] 51[1] 52[0] 53[1] 54[0] 55[1] 56[0] 57[1] 58[0] 59[1] 60[0] 61[1] 62[0] 63[1] 64[0] 65[1] 66[0] 67[1] 68[0] 69[1] 70[0] 71[1] 72[1] 73[0] 74[1] 75[0] 76[1] 77[0] 78[1] 79[0] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1] 87[0] 88[1] 89[0] 90[1] 91[0] 92[1] 93[0] 94[1] 95[0] 96[1] 97[0] 98[0] 99[1] 100[0]. For n=51, square set: 121 144 169 196. Grouping info for n=51: 51[0] 52[1] 53[0] 54[1] 55[0] 56[1] 57[0] 58[1] 59[0] 60[1] 61[0] 62[1] 63[0] 64[1] 65[0] 66[1] 67[0] 68[1] 69[0] 70[1] 71[0] 72[0] 73[1] 74[0] 75[1] 76[0] 77[1] 78[0] 79[1] 80[0] 81[1] 82[0] 83[1] 84[0] 85[1] 86[0] 87[1] 88[0] 89[1] 90[0] 91[1] 92[0] 93[1] 94[0] 95[1] 96[0] 97[1] 98[1] 99[0] 100[1] 101[0] 102[1]. For n=52, square set: 121 144 169 196. Grouping info for n=52: 52[0] 53[1] 54[0] 55[1] 56[0] 57[1] 58[0] 59[1] 60[0] 61[1] 62[0] 63[1] 64[0] 65[1] 66[0] 67[1] 68[0] 69[1] 70[0] 71[1] 72[1] 73[0] 74[1] 75[0] 76[1] 77[0] 78[1] 79[0] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1] 87[0] 88[1] 89[0] 90[1] 91[0] 92[1] 93[0] 94[1] 95[0] 96[1] 97[0] 98[0] 99[1] 100[0] 101[1] 102[0] 103[1] 104[0]. For n=53, square set: 121 144 169 196. Grouping info for n=53: 53[0] 54[1] 55[0] 56[1] 57[0] 58[1] 59[0] 60[1] 61[0] 62[1] 63[0] 64[1] 65[0] 66[1] 67[0] 68[1] 69[0] 70[1] 71[0] 72[0] 73[1] 74[0] 75[1] 76[0] 77[1] 78[0] 79[1] 80[0] 81[1] 82[0] 83[1] 84[0] 85[1] 86[0] 87[1] 88[0] 89[1] 90[0] 91[1] 92[0] 93[1] 94[0] 95[1] 96[0] 97[1] 98[1] 99[0] 100[1] 101[0] 102[1] 103[0] 104[1] 105[0] 106[1]. For n=54, square set: 121 144 169 196. Grouping info for n=54: 54[0] 55[1] 56[0] 57[1] 58[0] 59[1] 60[0] 61[1] 62[0] 63[1] 64[0] 65[1] 66[0] 67[1] 68[0] 69[1] 70[0] 71[1] 72[1] 73[0] 74[1] 75[0] 76[1] 77[0] 78[1] 79[0] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1] 87[0] 88[1] 89[0] 90[1] 91[0] 92[1] 93[0] 94[1] 95[0] 96[1] 97[0] 98[0] 99[1] 100[0] 101[1] 102[0] 103[1] 104[0] 105[1] 106[0] 107[1] 108[0]. For n=55, square set: 121 144 169 196. Grouping info for n=55: 55[0] 56[1] 57[0] 58[1] 59[0] 60[1] 61[0] 62[1] 63[0] 64[1] 65[0] 66[1] 67[0] 68[1] 69[0] 70[1] 71[0] 72[0] 73[1] 74[0] 75[1] 76[0] 77[1] 78[0] 79[1] 80[0] 81[1] 82[0] 83[1] 84[0] 85[1] 86[0] 87[1] 88[0] 89[1] 90[0] 91[1] 92[0] 93[1] 94[0] 95[1] 96[0] 97[1] 98[1] 99[0] 100[1] 101[0] 102[1] 103[0] 104[1] 105[0] 106[1] 107[0] 108[1] 109[0] 110[1]. For n=56, square set: 121 144 169 196. Grouping info for n=56: 56[0] 57[1] 58[0] 59[1] 60[0] 61[1] 62[0] 63[1] 64[0] 65[1] 66[0] 67[1] 68[0] 69[1] 70[0] 71[1] 72[1] 73[0] 74[1] 75[0] 76[1] 77[0] 78[1] 79[0] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1] 87[0] 88[1] 89[0] 90[1] 91[0] 92[1] 93[0] 94[1] 95[0] 96[1] 97[0] 98[0] 99[1] 100[0] 101[1] 102[0] 103[1] 104[0] 105[1] 106[0] 107[1] 108[0] 109[1] 110[0] 111[1] 112[0]. For n=57, square set: 121 144 169 196 225. Grouping info for n=57: 57[0] 58[1] 59[0] 60[1] 61[0] 62[1] 63[0] 64[1] 65[0] 66[1] 67[0] 68[1] 69[0] 70[1] 71[0] 72[0] 73[1] 74[0] 75[1] 76[0] 77[1] 78[0] 79[1] 80[0] 81[1] 82[0] 83[1] 84[0] 85[1] 86[0] 87[1] 88[0] 89[1] 90[0] 91[1] 92[0] 93[1] 94[0] 95[1] 96[0] 97[1] 98[1] 99[0] 100[1] 101[0] 102[1] 103[0] 104[1] 105[0] 106[1] 107[0] 108[1] 109[0] 110[1] 111[0] 112[1] 113[0] 114[1]. For n=58, square set: 121 144 169 196 225. Grouping info for n=58: 58[0] 59[1] 60[0] 61[1] 62[0] 63[1] 64[0] 65[1] 66[0] 67[1] 68[0] 69[1] 70[0] 71[1] 72[1] 73[0] 74[1] 75[0] 76[1] 77[0] 78[1] 79[0] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1] 87[0] 88[1] 89[0] 90[1] 91[0] 92[1] 93[0] 94[1] 95[0] 96[1] 97[0] 98[0] 99[1] 100[0] 101[1] 102[0] 103[1] 104[0] 105[1] 106[0] 107[1] 108[0] 109[1] 110[0] 111[1] 112[0] 113[1] 114[0] 115[1] 116[0]. For n=59, square set: 121 144 169 196 225. Grouping info for n=59: 59[0] 60[1] 61[0] 62[1] 63[0] 64[1] 65[0] 66[1] 67[0] 68[1] 69[0] 70[1] 71[0] 72[0] 73[1] 74[0] 75[1] 76[0] 77[1] 78[0] 79[1] 80[0] 81[1] 82[0] 83[1] 84[0] 85[1] 86[0] 87[1] 88[0] 89[1] 90[0] 91[1] 92[0] 93[1] 94[0] 95[1] 96[0] 97[1] 98[1] 99[0] 100[1] 101[0] 102[1] 103[0] 104[1] 105[0] 106[1] 107[0] 108[1] 109[0] 110[1] 111[0] 112[1] 113[0] 114[1] 115[0] 116[1] 117[0] 118[1]. For n=60, square set: 121 144 169 196 225. Grouping info for n=60: 60[0] 61[1] 62[0] 63[1] 64[0] 65[1] 66[0] 67[1] 68[0] 69[1] 70[0] 71[1] 72[1] 73[0] 74[1] 75[0] 76[1] 77[0] 78[1] 79[0] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1] 87[0] 88[1] 89[0] 90[1] 91[0] 92[1] 93[0] 94[1] 95[0] 96[1] 97[0] 98[0] 99[1] 100[0] 101[1] 102[0] 103[1] 104[0] 105[1] 106[0] 107[1] 108[0] 109[1] 110[0] 111[1] 112[0] 113[1] 114[0] 115[1] 116[0] 117[1] 118[0] 119[1] 120[0]. For n=61, square set: 144 169 196 225. Grouping info for n=61: 61[0] 62[1] 63[0] 64[1] 65[0] 66[1] 67[0] 68[1] 69[0] 70[1] 71[0] 72[0] 73[1] 74[0] 75[1] 76[0] 77[1] 78[0] 79[1] 80[0] 81[1] 82[0] 83[1] 84[0] 85[1] 86[0] 87[1] 88[0] 89[1] 90[0] 91[1] 92[0] 93[1] 94[0] 95[1] 96[0] 97[1] 98[1] 99[0] 100[1] 101[0] 102[1] 103[0] 104[1] 105[0] 106[1] 107[0] 108[1] 109[0] 110[1] 111[0] 112[1] 113[0] 114[1] 115[0] 116[1] 117[0] 118[1] 119[0] 120[1] 121[0] 122[1]. For n=62, square set: 144 169 196 225. Grouping info for n=62: 62[0] 63[1] 64[0] 65[1] 66[0] 67[1] 68[0] 69[1] 70[0] 71[1] 72[1] 73[0] 74[1] 75[0] 76[1] 77[0] 78[1] 79[0] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1] 87[0] 88[1] 89[0] 90[1] 91[0] 92[1] 93[0] 94[1] 95[0] 96[1] 97[0] 98[0] 99[1] 100[0] 101[1] 102[0] 103[1] 104[0] 105[1] 106[0] 107[1] 108[0] 109[1] 110[0] 111[1] 112[0] 113[1] 114[0] 115[1] 116[0] 117[1] 118[0] 119[1] 120[0] 121[1] 122[0] 123[1] 124[0]. CAN-list: 50 51 52 53 54 55 56 57 58 59 60 61 62. NOT-list: 48 49.
n = 48, 49 都是不可分的情形，这与上一篇的分析是相符的。n = 48 的情形存在 3 数环：48, 73, 96；而 n = 49 的情形，不存在 3 数环，但存在 5 数环：49, 51, 70, 74, 95。
n = 50, 51, ..., 62 都是可分的情形。
n = 63 到 77 的运行结果分析
PS H:\Read\num\Release> .\grouping The 1st number please: 63 For n=63, square set: 144 169 196 225. a=70, b=99, c=126. For n=64, square set: 144 169 196 225. a=70, b=99, c=126. For n=65, square set: 144 169 196 225 256. a=70, b=99, c=126. For n=66, square set: 144 169 196 225 256. a=70, b=99, c=126. For n=67, square set: 144 169 196 225 256. a=70, b=99, c=126. For n=68, square set: 144 169 196 225 256. a=70, b=99, c=126. For n=69, square set: 144 169 196 225 256. a=70, b=99, c=126. For n=70, square set: 144 169 196 225 256. a=70, b=99, c=126. For n=71, square set: 144 169 196 225 256. n=71: 96 must belong to both groups when dealing 100! Grouping info for n=71: 71[0] 73[1] 96[0] 98[1] 123[0] 125[1] 127[0]. Pending info: 100[0] 131[0] 100[1] 129[1] 102[1] 133[1] 129[1]. For n=72, square set: 169 196 225 256. Grouping info for n=72: 72[0] 73[1] 74[0] 75[1] 76[0] 77[1] 78[0] 79[1] 80[0] 81[1] 82[0] 83[1] 84[0] 85[1] 86[0] 87[1] 88[0] 89[1] 90[0] 91[1] 92[0] 93[1] 94[0] 95[1] 96[0] 97[1] 98[1] 99[0] 100[1] 101[0] 102[1] 103[0] 104[1] 105[0] 106[1] 107[0] 108[1] 109[0] 110[1] 111[0] 112[1] 113[0] 114[1] 115[0] 116[1] 117[0] 118[1] 119[0] 120[1] 121[0] 122[1] 123[0] 124[1] 125[0] 126[1] 127[0] 128[0] 129[1] 130[0] 131[1] 132[0] 133[1] 134[0] 135[1] 136[0] 137[1] 138[0] 139[1] 140[0] 141[1] 142[0] 143[1] 144[0]. For n=73, square set: 169 196 225 256 289. Grouping info for n=73: 73[0] 74[1] 75[0] 76[1] 77[0] 78[1] 79[0] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1] 87[0] 88[1] 89[0] 90[1] 91[0] 92[1] 93[0] 94[1] 95[0] 96[1] 97[0] 98[0] 99[1] 100[0] 101[1] 102[0] 103[1] 104[0] 105[1] 106[0] 107[1] 108[0] 109[1] 110[0] 111[1] 112[0] 113[1] 114[0] 115[1] 116[0] 117[1] 118[0] 119[1] 120[0] 121[1] 122[0] 123[1] 124[0] 125[1] 126[0] 127[1] 128[1] 129[0] 130[1] 131[0] 132[1] 133[0] 134[1] 135[0] 136[1] 137[0] 138[1] 139[0] 140[1] 141[0] 142[1] 143[0] 144[1] 145[0] 146[1]. For n=74, square set: 169 196 225 256 289. Grouping info for n=74: 74[0] 75[1] 76[0] 77[1] 78[0] 79[1] 80[0] 81[1] 82[0] 83[1] 84[0] 85[1] 86[0] 87[1] 88[0] 89[1] 90[0] 91[1] 92[0] 93[1] 94[0] 95[1] 96[0] 97[1] 98[1] 99[0] 100[1] 101[0] 102[1] 103[0] 104[1] 105[0] 106[1] 107[0] 108[1] 109[0] 110[1] 111[0] 112[1] 113[0] 114[1] 115[0] 116[1] 117[0] 118[1] 119[0] 120[1] 121[0] 122[1] 123[0] 124[1] 125[0] 126[1] 127[0] 128[0] 129[1] 130[0] 131[1] 132[0] 133[1] 134[0] 135[1] 136[0] 137[1] 138[0] 139[1] 140[0] 141[1] 142[0] 143[1] 144[0] 145[1] 146[0] 147[1] 148[0]. For n=75, square set: 169 196 225 256 289. Grouping info for n=75: 75[0] 76[1] 77[0] 78[1] 79[0] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1] 87[0] 88[1] 89[0] 90[1] 91[0] 92[1] 93[0] 94[1] 95[0] 96[1] 97[0] 98[0] 99[1] 100[0] 101[1] 102[0] 103[1] 104[0] 105[1] 106[0] 107[1] 108[0] 109[1] 110[0] 111[1] 112[0] 113[1] 114[0] 115[1] 116[0] 117[1] 118[0] 119[1] 120[0] 121[1] 122[0] 123[1] 124[0] 125[1] 126[0] 127[1] 128[1] 129[0] 130[1] 131[0] 132[1] 133[0] 134[1] 135[0] 136[1] 137[0] 138[1] 139[0] 140[1] 141[0] 142[1] 143[0] 144[1] 145[0] 146[1] 147[0] 148[1] 149[0] 150[1]. For n=76, square set: 169 196 225 256 289. Grouping info for n=76: 76[0] 77[1] 78[0] 79[1] 80[0] 81[1] 82[0] 83[1] 84[0] 85[1] 86[0] 87[1] 88[0] 89[1] 90[0] 91[1] 92[0] 93[1] 94[0] 95[1] 96[0] 97[1] 98[1] 99[0] 100[1] 101[0] 102[1] 103[0] 104[1] 105[0] 106[1] 107[0] 108[1] 109[0] 110[1] 111[0] 112[1] 113[0] 114[1] 115[0] 116[1] 117[0] 118[1] 119[0] 120[1] 121[0] 122[1] 123[0] 124[1] 125[0] 126[1] 127[0] 128[0] 129[1] 130[0] 131[1] 132[0] 133[1] 134[0] 135[1] 136[0] 137[1] 138[0] 139[1] 140[0] 141[1] 142[0] 143[1] 144[0] 145[1] 146[0] 147[1] 148[0] 149[1] 150[0] 151[1] 152[0]. For n=77, square set: 169 196 225 256 289. Grouping info for n=77: 77[0] 78[1] 79[0] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1] 87[0] 88[1] 89[0] 90[1] 91[0] 92[1] 93[0] 94[1] 95[0] 96[1] 97[0] 98[0] 99[1] 100[0] 101[1] 102[0] 103[1] 104[0] 105[1] 106[0] 107[1] 108[0] 109[1] 110[0] 111[1] 112[0] 113[1] 114[0] 115[1] 116[0] 117[1] 118[0] 119[1] 120[0] 121[1] 122[0] 123[1] 124[0] 125[1] 126[0] 127[1] 128[1] 129[0] 130[1] 131[0] 132[1] 133[0] 134[1] 135[0] 136[1] 137[0] 138[1] 139[0] 140[1] 141[0] 142[1] 143[0] 144[1] 145[0] 146[1] 147[0] 148[1] 149[0] 150[1] 151[0] 152[1] 153[0] 154[1]. CAN-list: 72 73 74 75 76 77. NOT-list: 63 64 65 66 67 68 69 70 71.
n = 63, 64, ..., 70 都是不可分的情形，都是存在 3 数环：70, 99, 126。而 n = 71 为不可分的情形，不存在 3 数环，但存在 5 数环：71, 73, 96, 100, 125。
n = 72, 73, ..., 77 都是可分的情形。
n = 78 到 92 的运行结果分析
PS H:\Read\num\Release> .\grouping The 1st number please: 78 For n=78, square set: 169 196 225 256 289. Grouping info for n=78: 78[0] 79[1] 80[0] 81[1] 82[0] 83[1] 84[0] 85[1] 86[0] 87[1] 88[0] 89[1] 90[0] 91[1] 92[0] 93[1] 94[0] 95[1] 96[0] 97[1] 98[1] 99[0] 100[1] 101[0] 102[1] 103[0] 104[1] 105[0] 106[1] 107[0] 108[1] 109[0] 110[1] 111[0] 112[1] 113[0] 114[1] 115[0] 116[1] 117[0] 118[1] 119[0] 120[1] 121[0] 122[1] 123[0] 124[1] 125[0] 126[1] 127[0] 128[0] 129[1] 130[0] 131[1] 132[0] 133[1] 134[0] 135[1] 136[0] 137[1] 138[0] 139[1] 140[0] 141[1] 142[0] 143[1] 144[0] 145[1] 146[0] 147[1] 148[0] 149[1] 150[0] 151[1] 152[0] 153[1] 154[0] 155[1] 156[0]. For n=79, square set: 169 196 225 256 289. Grouping info for n=79: 79[0] 80[1] 81[0] 82[1] 83[0] 84[1] 85[0] 86[1] 87[0] 88[1] 89[0] 90[1] 91[0] 92[1] 93[0] 94[1] 95[0] 96[1] 97[0] 98[0] 99[1] 100[0] 101[1] 102[0] 103[1] 104[0] 105[1] 106[0] 107[1] 108[0] 109[1] 110[0] 111[1] 112[0] 113[1] 114[0] 115[1] 116[0] 117[1] 118[0] 119[1] 120[0] 121[1] 122[0] 123[1] 124[0] 125[1] 126[0] 127[1] 128[1] 129[0] 130[1] 131[0] 132[1] 133[0] 134[1] 135[0] 136[1] 137[0] 138[1] 139[0] 140[1] 141[0] 142[1] 143[0] 144[1] 145[0] 146[1] 147[0] 148[1] 149[0] 150[1] 151[0] 152[1] 153[0] 154[1] 155[0] 156[1] 157[0] 158[1]. For n=80, square set: 169 196 225 256 289. a=96, b=129, c=160. For n=81, square set: 169 196 225 256 289. a=96, b=129, c=160. For n=82, square set: 169 196 225 256 289 324. a=96, b=129, c=160. For n=83, square set: 169 196 225 256 289 324. a=96, b=129, c=160. For n=84, square set: 169 196 225 256 289 324. a=96, b=129, c=160. For n=85, square set: 196 225 256 289 324. a=96, b=129, c=160. For n=86, square set: 196 225 256 289 324. a=96, b=129, c=160. For n=87, square set: 196 225 256 289 324. a=96, b=129, c=160. For n=88, square set: 196 225 256 289 324. a=96, b=129, c=160. For n=89, square set: 196 225 256 289 324. a=96, b=129, c=160. For n=90, square set: 196 225 256 289 324. a=96, b=129, c=160. For n=91, square set: 196 225 256 289 324 361. a=96, b=129, c=160. For n=92, square set: 196 225 256 289 324 361. a=96, b=129, c=160. CAN-list: 78 79. NOT-list: 80 81 82 83 84 85 86 87 88 89 90 91 92.
n = 78, 79 还是可分的情形。n = 80, 81, ..., 92 则都是不可分的情形，且都有 3 数环：96, 129, 160。
n = 93 到 100 的运行结果分析
PS H:\Read\num\Release> .\grouping The 1st number please: 93 For n=93, square set: 196 225 256 289 324 361. a=96, b=129, c=160. For n=94, square set: 196 225 256 289 324 361. a=96, b=129, c=160. For n=95, square set: 196 225 256 289 324 361. a=96, b=129, c=160. For n=96, square set: 196 225 256 289 324 361. a=96, b=129, c=160. For n=97, square set: 196 225 256 289 324 361. n=97: 126 must belong to both groups when dealing 130! Grouping info for n=97: 97[0] 99[1] 126[0] 128[1] 157[0] 159[1] 161[0] 190[0] 192[1]. Pending info: 130[0] 165[0] 132[0] 169[0] 130[1] 163[1] 132[1] 167[1] 134[1] 171[1] 163[1]. For n=98, square set: 225 256 289 324 361. Grouping info for n=98: 98[0] 99[1] 100[0] 101[1] 102[0] 103[1] 104[0] 105[1] 106[0] 107[1] 108[0] 109[1] 110[0] 111[1] 112[0] 113[1] 114[0] 115[1] 116[0] 117[1] 118[0] 119[1] 120[0] 121[1] 122[0] 123[1] 124[0] 125[1] 126[0] 127[1] 128[1] 129[0] 130[1] 131[0] 132[1] 133[0] 134[1] 135[0] 136[1] 137[0] 138[1] 139[0] 140[1] 141[0] 142[1] 143[0] 144[1] 145[0] 146[1] 147[0] 148[1] 149[0] 150[1] 151[0] 152[1] 153[0] 154[1] 155[0] 156[1] 157[0] 158[1] 159[0] 160[1] 161[0] 162[0] 163[1] 164[0] 165[1] 166[0] 167[1] 168[0] 169[1] 170[0] 171[1] 172[0] 173[1] 174[0] 175[1] 176[0] 177[1] 178[0] 179[1] 180[0] 181[1] 182[0] 183[1] 184[0] 185[1] 186[0] 187[1] 188[0] 189[1] 190[0] 191[1] 192[0] 193[1] 194[0] 195[1] 196[0]. For n=99, square set: 225 256 289 324 361. a=126, b=163, c=198. For n=100, square set: 225 256 289 324 361. a=126, b=163, c=198. CAN-list: 98. NOT-list: 93 94 95 96 97 99 100.
n = 93, 94, ..., 96 是不可分的情形，且都有 3 数环：96, 129, 160。
n = 97 也是不可分的情形，没有 3 数环，但有 5 数环：97, 99, 126, 130, 159。
n = 98 是可分的情形。
n = 99, 100 是不可分的情形，且都有 3 数环：126, 163, 198。
至此，拓展三的第 2 问的答案明确了，是 k = 99。
这篇关于IMO 2021 第 1 题拓展问题的两个极值的编程求解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门：从零开始的编程之旅
- 2024-11-23Java创业入门：新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门：初学者的简单教程
- 2024-11-23JAVA副业入门：初学者的实战指南
