#P1489. Egyptian Multiplication

Egyptian Multiplication

题目描述:
1858年,苏格兰古物学家A. Henry Rhind获得了一份被称为"莱因德纸草书"的文献。这份题为"获取所有隐秘知识指南"的文献,为研究古埃及算术提供了重要线索。

该数字系统没有零的概念,使用不同符号表示不同数量级:

  • | 表示1(注意是竖线符号,不是数字1)
  • n 表示10
  • 9 表示100
  • 8 表示1000
  • r 表示10000 (实际埃及象形文字比这些现代符号更具象形特征。本题不考虑大于99,999的数字)

数字书写时,从个位到万位依次排列各组符号。例如数字4,023表示为:||| nn 8888。零用对应符号组的空缺表示,如40,230表示为:nnn 99 rrrr。(实际纸草书中这些组可能跨行书写,但本题要求单行书写)

埃及人的乘法运算使用双栏法:

  1. 左栏写|(1),右栏写被乘数a
  2. 不断对两栏数字进行倍增
  3. 当左栏数字不超过乘数b时停止倍增
  4. 标记左栏中相加等于b的数字(用*号)
  5. 将右栏对应*号的数字相加得到结果

示例展示了483×27的计算过程,最终结果为:| nnnn 888 r(即1+40+800+10,000=10,841)

输入:
多组埃及数字对,每组数字独占一行,符号组间用空格分隔(包括最后一组)。输入以空行结束。

输出:
对每对数字:

  1. 打印埃及乘法步骤
  2. 左栏数字左对齐
  3. 各符号组以空格结尾(包括最后一组)
  4. 若有*号,与左栏数字间隔一个空格
  5. 右栏数字从第35列开始
  6. 最后打印"The solution is: "和乘积的埃及表示

示例输入1:

||
||
||| 
|||| 
nnnnnn 9 
||| n 
n 
9 
||| 
8

示例输出1:

|                                 || 
|| *                              |||| 
The solution is: ||||
|                                 ||| 
||                                |||||| 
|||| *                            || n 
The solution is: || n 
| *                               nnnnnn 9 
||                                nn 999 
|||| *                            nnnn 999999 
|||||||| *                        nnnnnnnn 99 8 
The solution is: nnnnnnnn 88 
|                                 n 
||                                nn 
|||| *                            nnnn 
||||||||                          nnnnnnnn 
|||||| n                          nnnnnn 9 
|| nnn *                          nn 999 
|||| nnnnnn *                     nnnn 999999 
The solution is: 8 
|                                 ||| 
||                                |||||| 
||||                              || n 
|||||||| *                        |||| nn 
|||||| n                          |||||||| nnnn 
|| nnn *                          |||||| nnnnnnnnn 
|||| nnnnnn *                     || nnnnnnnnn 9 
|||||||| nn 9 *                   |||| nnnnnnnn 999 
|||||| nnnnn 99 *                 |||||||| nnnnnn 9999999 
|| n 99999 *                      |||||| nnn 99999 8 
The solution is: 888

来源:
East Central North America 1994