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。

 

上一篇:我如何将这些XDocuments分组?


下一篇:长文本知识抽取:基于语义分割的文档级三元组关系抽取《Document-level Relation Extraction as Semantic Segmentation》