平方和球柱的容量：Karatsuba 精确平方¶
最大数量的证明¶
记 \(C(n)=\lfloor(n+1)^2/2\rfloor-1\) .
上界。 设已经放入了 \(T=C(n)+1=\lfloor(n+1)^2/2\rfloor\) 个球。考察最大的 \(n+1\) 个编号，即 \(T-n,\ldots,T\) .其中任意两个不同编号之和严格大于 \(n^2\) 且严格小于 \((n+1)^2\) ，所以不能相邻。每根柱子的编号从底到顶严格递增，这些大编号在该柱上必然构成连续的顶端部分；若某柱有两个，就会有两个相邻的大编号，产生矛盾。因此需要至少 \(n+1\) 根柱子，上界成立。
达到上界的构造。 一根柱子只放球一。对于奇数 \(n>1\) ，在当前 \(n\) 根柱子上放两层，从顶到底描述如下，局部列编号为 \(j=0,\ldots,n-1\) ：
再在中间 \(n-2\) 根柱子的下方递归放入规模 \(n-2\) 的方案。上下两层相邻和为 \(n^2\) ；第二层与递归部分第一层的相邻和为 \((n-1)^2\) .剩余相邻关系由归纳保证。两层使用最大的 \(2n\) 个编号，因为 \(C(n)-C(n-2)=2n\) ，所有编号不重不漏。
对于偶数 \(n\) ，最上层从左到右为 \(C(n),C(n)-1,\ldots,C(n)-n+1\) ，前 \(n-1\) 根柱子的下方放规模 \(n-1\) 的方案。相接两层的编号和为 \(n^2\) ，并且 \(C(n)-C(n-1)=n\) .故也合法且恰好用尽一到 \(C(n)\) .
所有列从顶到底严格递减，因此逆向按编号从小到大放入，正好遵守原操作时序。构造与上界合起来证明最优数量就是 \(C(n)\) .
三次递归平方¶
将 \(N+1\) 写成低位在前的万进制数字多项式，补零到二次幂长度。分成低半部分 \(A\) 与高半部分 \(B\) ，设半长为 \(h\) ：
只递归计算 \(A^2,B^2,(A+B)^2\) 三个平方，再线性合并。长度不超过三十二时，用普通乘法，利用平方的对称性将非对角项乘二。递归期间暂不进位；完整卷积算出后统一万进制进位，再除以二、减一，输出 \(\lfloor(N+1)^2/2\rfloor-1\) .
正确性与数值安全¶
分治恒等式准确给出平方的低、中、高三段；归纳可知每次递归返回精确的卷积系数。进位不改变数字值，除二取整与减一计算容量公式，因此答案正确。
最多有 \(25001\) 个万进制位，原始数字和不超过 \(25001\times9999\) .每次把高低半部相加都保持总和，因此任意递归子问题的所有非负卷积系数总和不超过 \((25001\times9999)^2<2^{63}\) .中间的两项减法得到非负交叉项；所有被减部分及累计结果也在这个界内，所以标准有符号 64 位整数足够，无须扩展整数或浮点数。
复杂度与适用范围¶
若规范化数字长度为 \(d\) ，递推为 \(T(d)=3T(d/2)+O(d)\) ，故时间为 \(O(d^{\log_2 3})\) ，同时存活的向量总大小构成几何级数，额外空间为 \(O(d)\) .另计读入原始字符串的线性时间与空间；多组数据的时间求和，空间取最大值。
alternative.cpp 支持完整范围，独立于模数和单位根，展示纯整数分治乘法。首选NTT 平方具有更低的渐进时间。Karatsuba 是经典算法；GPT-6 提供本题的应用、64 位数值界、程序和验证。容量公式与构造证明来自出题人解法。两种大整数程序均与 Python 精确整数比较，见测量记录。