新未名空间

做了S(7)后，做S(2002)需要再加下面几项。但overflow很严重，是这题的一个卡点。64-bit的普通计算机没法处理2^64或以上的整数（20位或以上）。但搞数学计算或者相关专业的人应该能得心应手地处理吧？这些专业应该有常用工具做这种大整数运算，否则那种专业就太对不起学生了。本题特殊，只要求最低的16位，除法比较简单，最坏的overflow是34位（如果不做按照case的简化），因此还是可以写个个人程序处理这个问题的，但可能要稍微花点时间，需要拿学分的人去干。（这也许是个学校某专业的作业题吧？普通专业应该不会学怎样处理这类问题。）

对了，要保持一致的整数性，会有必要把最后面的那个乘法提前完成,因此2被提到了最前。还有就是：如果要算此类数的总数，只要把开始的那个2去掉，把最后那个乘数去掉，然后用那个（m，k）标识里的k*n代替它们，同样地进行计算即可。

长度8
11111117 (7,1)
2(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(n-7)/7!*7

11111128 11111139 (17,2)
2(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(n-7)/6!*17

11111229 (9,1)
2(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(n-7)/5!/2!*9


长度9
111111118 (8,1)
2(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(n-7)(n-8)/8!*8

111111129 (9,1)
2(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(n-7)(n-8)/7!*9

长度10
1111111119 (9,1)
2(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(n-7)(n-8)(n-9)/9!*9

对n=2022,如果算和也算此类数的总数。所有的26个类型（和与总数）的2x26=52个类型中近一半overflow。

如果不用工具，可以编个计算机程序先把这些贡献项进行如下处理。把除法约化后，这个项会是一系列整数的乘法。把因子按照大小排序。最大与最小乘法，次最大与次最小乘，两者中小者乘剩下的最大，大者乘剩下的最小，直到两个到一个范围内（比如10位数到16位之间）为止。剩下的继续分。。。

这样的数可被写成a*10^m + b的形式，b是m=9位，a是7位。概念上用a和b表示这个数。
然后用
(a*10^m+b)(c*10^m+d) = ab*10^(2m)+10^m*(bc+ad) +cd找到此积的概念表示数字对。第一项被弃掉，其它项之和没有overflow，取最低的16位，然后按前7和后9位数位得出A和B。
如此下去。。。

对这个题，要做26次左右overflow处理。利用上述那个公式26次左右。

这种方法对更大的n也可用，但会较快变得不有效。应该有些已经比较标准化的方法与系统挂钩了，会很好用。但这对绝大多数搞“普通”计算的人应该是很偏门的。大家肯定是找自己犯了什么错。

meiyoumajia 写了： 2023年 2月 24日 23:21 还是算下去吧。练习counting和大整数的计算。：-）

哈哈。能算肯定是要算下去的。一个想法在完全冷却之前不可能放弃的。

这个讨论很好。数学其实和工程一样，也是各种想办法。