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 题拓展问题的两个极值的编程求解