[题解] 时隔一年,再谈 Elegant Square
前言
人类玩的太差了。
本文为 Elegant Square - Problem - QOJ.ac 的数据范围下最优构造题解。
正文
我们之前在 [笔记] 关于正交拉丁方的构造与应用 - 沉石鱼惊旋 的博客 里写到:本题使用一对正交拉丁方的构造,一组填质数一组填 Square-Free 的数,就能做到一个很优的解。在本题
但是这不是最优的解。甚至我们可以找到一个疑似下界的值,搭配一些强力搜索,可以构造得到下界。总之,结论是本题在
提交记录在:Submission #3475822 - QOJ.ac。代码有 55kb,因为直接把表写进去了。浏览器有加载不出的风险,谨慎观看。代码可直接在 ElegantSquare.cpp 下载。
甚至因为不存在一对
我们先只保留在
我们先讨论集合
继续拓展这一做法。
删除倍数少于
这里 GPT 神力给了个很不是人的做法:
我们为每个
我们声称如果最大元素不超过
证明考虑对任意
实际上对于
取
它的直接含义是,选中的数中,含
而
带入
至于为什么可以得到
令
这个东西可以利用
所以
附录
A
A.1 n=3 ,下界 L=21
- 排除的上限为
M=20 。 - 初始平方自由候选有 13 个,安全删除后剩 7 个。
- 取
P=\varnothing ,t=1 。 - 素数容量之和
A=0 。 -
- 必要条件要求
9=tn^2\le A+B=7 ,与7<9 矛盾。 - 因此
F(3)\ge21 。
A.2 n=4 ,下界 L=65
- 排除的上限为
M=64 。 - 初始平方自由候选有 39 个,安全删除后剩 17 个。
- 取
P=\{2,3,5,7,11\} ,t=2 。 - 素数容量之和
A=20 。 -
- 必要条件要求
32=tn^2\le A+B=27 ,与27<32 矛盾。 - 因此
F(4)\ge65 。
A.3 n=5 ,下界 L=102
- 排除的上限为
M=101 。 - 初始平方自由候选有 62 个,安全删除后剩 26 个。
- 取
P=\{5,7\} ,t=1 。 - 素数容量之和
A=10 。 -
- 必要条件要求
25=tn^2\le A+B=22 ,与22<25 矛盾。 - 因此
F(5)\ge102 。
A.4 n=6 ,下界 L=154
- 排除的上限为
M=153 。 - 初始平方自由候选有 93 个,安全删除后剩 42 个。
- 取
P=\{2,7\} ,t=1 。 - 素数容量之和
A=18 。 -
- 必要条件要求
36=tn^2\le A+B=35 ,与35<36 矛盾。 - 因此
F(6)\ge154 。
A.5 n=7 ,下界 L=231
- 排除的上限为
M=230 。 - 初始平方自由候选有 143 个,安全删除后剩 59 个。
- 取
P=\{3,5,7,11,13,17,19,23\} ,t=2 。 - 素数容量之和
A=77 。 -
- 必要条件要求
98=tn^2\le A+B=97 ,与97<98 矛盾。 - 因此
F(7)\ge231 。
A.6 n=8 ,下界 L=319
- 排除的上限为
M=318 。 - 初始平方自由候选有 195 个,安全删除后剩 69 个。
- 取
P=\{5,7,11,13,17,19,23\} ,t=2 。 - 素数容量之和
A=72 。 -
- 必要条件要求
128=tn^2\le A+B=108 ,与108<128 矛盾。 - 因此
F(8)\ge319 。
A.7 n=9 ,下界 L=403
- 排除的上限为
M=402 。 - 初始平方自由候选有 245 个,安全删除后剩 88 个。
- 取
P=\{13,17,19,23,29\} ,t=1 。 - 素数容量之和
A=45 。 -
- 必要条件要求
81=tn^2\le A+B=73 ,与73<81 矛盾。 - 因此
F(9)\ge403 。
A.8 n=10 ,下界 L=518
- 排除的上限为
M=517 。 - 初始平方自由候选有 317 个,安全删除后剩 112 个。
- 取
P=\{17,19,23,29,31\} ,t=1 。 - 素数容量之和
A=50 。 -
- 必要条件要求
100=tn^2\le A+B=94 ,与94<100 矛盾。 - 因此
F(10)\ge518 。
A.9 n=11 ,下界 L=629
- 排除的上限为
M=628 。 - 初始平方自由候选有 383 个,安全删除后剩 144 个。
- 取
P=\{5,7,11,13,17,19,23,29,31,37,41\} ,t=2 。 - 素数容量之和
A=187 。 -
- 必要条件要求
242=tn^2\le A+B=239 ,与239<242 矛盾。 - 因此
F(11)\ge629 。
A.10 n=12 ,下界 L=731
- 排除的上限为
M=730 。 - 初始平方自由候选有 445 个,安全删除后剩 158 个。
- 取
P=\{5,7,11,13,17,19,23,29,31,37,41\} ,t=2 。 - 素数容量之和
A=216 。 -
- 必要条件要求
288=tn^2\le A+B=268 ,与268<288 矛盾。 - 因此
F(12)\ge731 。
A.11 n=13 ,下界 L=893
- 排除的上限为
M=892 。 - 初始平方自由候选有 541 个,安全删除后剩 187 个。
- 取
P=\{5,7,11,13,17,19,23,29,31,37,41,43\} ,t=2 。 - 素数容量之和
A=260 。 -
- 必要条件要求
338=tn^2\le A+B=316 ,与316<338 矛盾。 - 因此
F(13)\ge893 。
A.12 n=14 ,下界 L=1085
- 排除的上限为
M=1084 。 - 初始平方自由候选有 657 个,安全删除后剩 225 个。
- 取
P=\{7,11,13,17,19,23,29,31,37,41,43,47\} ,t=2 。 - 素数容量之和
A=280 。 -
- 必要条件要求
392=tn^2\le A+B=388 ,与388<392 矛盾。 - 因此
F(14)\ge1085 。
A.13 n=15 ,下界 L=1222
- 排除的上限为
M=1221 。 - 初始平方自由候选有 743 个,安全删除后剩 257 个。
- 取
P=\{7,11,13,17,19,23,29,31,37,41,43,47,53\} ,t=2 。 - 素数容量之和
A=330 。 -
- 必要条件要求
450=tn^2\le A+B=446 ,与446<450 矛盾。 - 因此
F(15)\ge1222 。
A.14 n=16 ,下界 L=1403
- 排除的上限为
M=1402 。 - 初始平方自由候选有 856 个,安全删除后剩 295 个。
- 取
P=\{7,11,13,17,19,23,29,31,37,41,43,47,53,59\} ,t=2 。 - 素数容量之和
A=384 。 -
- 必要条件要求
512=tn^2\le A+B=509 ,与509<512 矛盾。 - 因此
F(16)\ge1403 。
A.15 n=17 ,下界 L=1742
- 排除的上限为
M=1741 。 - 初始平方自由候选有 1059 个,安全删除后剩 353 个。
- 取
P=\{7,11,13,17,19,23,29,31,37,41,43,47,53,59,61\} ,t=2 。 - 素数容量之和
A=442 。 -
- 必要条件要求
578=tn^2\le A+B=576 ,与576<578 矛盾。 - 因此
F(17)\ge1742 。
A.16 n=18 ,下界 L=1943
- 排除的上限为
M=1942 。 - 初始平方自由候选有 1179 个,安全删除后剩 377 个。
- 取
P=\{7,11,13,17,19,23,29,31,37,41,43,47,53,59,61\} ,t=2 。 - 素数容量之和
A=504 。 -
- 必要条件要求
648=tn^2\le A+B=640 ,与640<648 矛盾。 - 因此
F(18)\ge1943 。
A.17 n=19 ,下界 L=2130
- 排除的上限为
M=2129 。 - 初始平方自由候选有 1294 个,安全删除后剩 420 个。
- 取
P=\{19,37,41,43,47,53,59,61\} ,t=1 。 - 素数容量之和
A=171 。 -
- 必要条件要求
361=tn^2\le A+B=360 ,与360<361 矛盾。 - 因此
F(19)\ge2130 。
原始证书保存
A.18 n=20 ,下界 L=2263
- 排除的上限为
M=2262 。 - 初始平方自由候选有 1375 个,安全删除后剩 459 个。
- 取
P=\{23,37,41,43,47,53,59,61\} ,t=1 。 - 素数容量之和
A=180 。 -
- 必要条件要求
400=tn^2\le A+B=399 ,与399<400 矛盾。 - 因此
F(20)\ge2263 。
原始证书保存
A.19 n=21 ,下界 L=2553
- 排除的上限为
M=2552 。 - 初始平方自由候选有 1551 个,安全删除后剩 517 个。
- 取
P=\{11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73\} ,t=2 。 - 素数容量之和
A=609 。 -
- 必要条件要求
882=tn^2\le A+B=870 ,与870<882 矛盾。 - 因此
F(21)\ge2553 。
A.20 n=22 ,下界 L=2686
- 排除的上限为
M=2685 。 - 初始平方自由候选有 1633 个,安全删除后剩 532 个。
- 取
P=\{11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73\} ,t=2 。 - 素数容量之和
A=660 。 -
- 必要条件要求
968=tn^2\le A+B=924 ,与924<968 矛盾。 - 因此
F(22)\ge2686 。
A.21 n=23 ,下界 L=3034
- 排除的上限为
M=3033 。 - 初始平方自由候选有 1845 个,安全删除后剩 622 个。
- 取
P=\{7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83\} ,t=2 。 - 素数容量之和
A=874 。 -
- 必要条件要求
1058=tn^2\le A+B=1050 ,与1050<1058 矛盾。 - 因此
F(23)\ge3034 。
A.22 n=24 ,下界 L=3293
- 排除的上限为
M=3292 。 - 初始平方自由候选有 2003 个,安全删除后剩 658 个。
- 取
P=\{7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83\} ,t=2 。 - 素数容量之和
A=960 。 -
- 必要条件要求
1152=tn^2\le A+B=1136 ,与1136<1152 矛盾。 - 因此
F(24)\ge3293 。
A.23 n=25 ,下界 L=3619
- 排除的上限为
M=3618 。 - 初始平方自由候选有 2203 个,安全删除后剩 722 个。
- 取
P=\{11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89\} ,t=2 。 - 素数容量之和
A=925 。 -
- 必要条件要求
1250=tn^2\le A+B=1237 ,与1237<1250 矛盾。 - 因此
F(25)\ge3619 。
A.24 n=26 ,下界 L=3910
- 排除的上限为
M=3909 。 - 初始平方自由候选有 2377 个,安全删除后剩 784 个。
- 取
P=\{13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97\} ,t=2 。 - 素数容量之和
A=884 。 -
- 必要条件要求
1352=tn^2\le A+B=1339 ,与1339<1352 矛盾。 - 因此
F(26)\ge3910 。
A.25 n=27 ,下界 L=4141
- 排除的上限为
M=4140 。 - 初始平方自由候选有 2518 个,安全删除后剩 813 个。
- 取
P=\{13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97\} ,t=2 。 - 素数容量之和
A=945 。 -
- 必要条件要求
1458=tn^2\le A+B=1408 ,与1408<1458 矛盾。 - 因此
F(27)\ge4141 。
A.26 n=28 ,下界 L=4494
- 排除的上限为
M=4493 。 - 初始平方自由候选有 2731 个,安全删除后剩 912 个。
- 取
P=\{11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103\} ,t=2 。 - 素数容量之和
A=1204 。 -
- 必要条件要求
1568=tn^2\le A+B=1562 ,与1562<1568 矛盾。 - 因此
F(28)\ge4494 。
A.27 n=29 ,下界 L=4674
- 排除的上限为
M=4673 。 - 初始平方自由候选有 2842 个,安全删除后剩 964 个。
- 取
P=\{11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107\} ,t=2 。 - 素数容量之和
A=1305 。 -
- 必要条件要求
1682=tn^2\le A+B=1677 ,与1677<1682 矛盾。 - 因此
F(29)\ge4674 。
A.28 n=30 ,下界 L=5014
- 排除的上限为
M=5013 。 - 初始平方自由候选有 3051 个,安全删除后剩 1012 个。
- 取
P=\{11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107\} ,t=2 。 - 素数容量之和
A=1380 。 -
- 必要条件要求
1800=tn^2\le A+B=1756 ,与1756<1800 矛盾。 - 因此
F(30)\ge5014 。