题意分析

题目要求实现古埃及乘法算法，将两个用特殊符号表示的埃及数字相乘。埃及数字使用以下符号表示：

• | 表示1
• n 表示10
• 9 表示100
• 8 表示1000
• r 表示10000

输入给出两个埃及数字，需要按照古埃及乘法步骤计算乘积，并输出计算过程和最终结果（仍用埃及数字表示）。

解题思路

1. 符号转换：

   • 将输入的埃及数字字符串转换为对应的整数值
   • 使用哈希表存储符号与数值的对应关系

2. 埃及乘法实现：

   • 采用双栏法：左栏从1开始不断倍增，右栏从被乘数开始倍增
   • 当左栏数字是乘数的二进制分解项时，标记该行并累加右栏对应值

3. 结果转换：

   • 将最终乘积转换回埃及数字表示形式
   • 按从低位到高位的顺序生成对应符号串

代码实现

#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>

using std::memset;
using std::map;
using std::cin;

long long a,b;
char stra[100], strb[100];
map<char,int> symbol;
char hash[10];

long long parseInt(char str[100], int len)
{
    long long ans = 0;
    for(int i = 0; i < len; i++)
    {
        if(str[i] != ' ')
            ans += symbol[str[i]];
    }
    return ans;
}

void parseString(long long a, char *str)
{
    int cnt = 0;
    int nbit = 0;
    while(a)
    {
        for(int i = 0; i < a%10; i++)
            str[cnt++] = hash[nbit];
        if(a%10 && a/10) str[cnt++] = ' ';
        a /= 10;
        nbit++;
    }
    str[cnt++] = '\0';
}

void cal(char stra[100], int lena, char strb[100], int lenb)
{
    long long a = parseInt(stra, lena);
    long long b = parseInt(strb, lenb);

    char mida[100], midb[100];
    long long m = 0;
    long long bit = 0;

    while(b)
    {
        parseString(1<<bit, mida);
        parseString(a, midb);

        long long lena1 = strlen(mida);
        long long lenb1 = strlen(midb);

        if(b&1)
        {
            m += a;
            printf("%s", mida);
            printf(" *");
            for(int i = 0; i < 32-lena1; i++)
                printf(" ");
            printf("%s\n", midb);
        }
        else
        {
            printf("%s", mida);
            for(int i = 0; i < 34-lena1; i++)
                printf(" ");
            printf("%s\n", midb);
        }
        a = a<<1;
        b = b>>1;
        bit++;
    }

    char ans[100];
    parseString(m, ans);
    printf("The solution is: ");
    printf("%s\n", ans);
}

void init()
{
    symbol['|'] = 1;
    symbol['n'] = 10;
    symbol['9'] = 100;
    symbol['8'] = 1000;
    symbol['r'] = 10000;

    hash[0] = '|';
    hash[1] = 'n';
    hash[2] = '9';
    hash[3] = '8';
    hash[4] = 'r';
}

int main()
{
    char stra[100], strb[100];
    init();
    while(cin.getline(stra, 100))
    {
        cin.getline(strb, 100);
        if(strlen(stra) && strlen(strb))
        {
            cal(stra, strlen(stra), strb, strlen(strb));
        }
    }
    return 0;
}