题解：P1001 A+B Problem

Wesley_Lin · 2025-05-10 14:36:44 · 题解

Update 2025.05.10：这里是小作坊（所以下的料有点猛），大号是 @W_C_B_H。

Update 2025.05.17：增加了 Part II。

Update 2025.07.30：修改了 Part II 中程序在遇到无效代码时的报错信息，并增加了快速幂的代码。

Update 2025.12.08：由于之前这里的代码被人说 AC 不了，故加上了 AC 记录。

Part I：64 位 0.5\text{MB} 内存的机器码虚拟机

注意到这道题我们可以通过手搓一个拥有 0.5\text{MB} 内存和 64 位系统的虚拟机来完成。

AC 记录：link。

代码实现

Code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned int
#define N 65536
int memory[N];
ull code[N] = {

};
/*
0 Input
1 Output
2 Write
3 Copy
4 Calculate (& | ~ ^ << >>)
5 Calculate (+ - * / %)
6 Goto
7 If-goto
8 x++
9 x--
f Exit
*/
signed main()
{
    for(int i=0;;i=(i+1)%N)
    {
        int op=code[i]>>60;
        if(op==0)       //Input
        {
            int p=code[i]&65535;
            cin >> memory[ (code[i]>>56)&1 ? memory[p] : p ];
        }
        else if(op==1)  //Output
        {
            int p=code[i]&65535, val = memory[ (code[i]>>56)&1 ? memory[p] : p ];
            if((code[i]>>57)&1)
            {
                cout<<char(val&127);
            }
            else
            {
                cout<<val;
            }
        }
        else if(op==2)  //Write
        {
            int p = (code[i]>>32)&65535, val = code[i]&((1ll<<32)-1);
            memory[ (code[i]>>56)&1 ? memory[p] : p ] = val;
        }
        else if(op==3)  //Copy
        {
            int pf = (code[i]>>16)&65535, pt = code[i]&65535;
            int val = memory[ (code[i]>>55)&1 ? memory[pf] : pf ];
            memory[ (code[i]>>56)&1 ? memory[pt] : pt ] = val;
        }
        else if(op==4)  //Calculate (& | ~ ^ << >>)
        {
            int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535;
            int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ],
            val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ], val3;
            int op2 = (code[i]>>52)&15;
            if(op2==0)
            {
                val3=val1&val2;
            }
            else if(op2==1)
            {
                val3=val1|val2;
            }
            else if(op2==2)
            {
                val3=~val2;
            }
            else if(op2==3)
            {
                val3=val1^val2;
            }
            else if(op2==4)
            {
                val3=((val2>>6)?0:val1<<val2);
            }
            else
            {
                val3=((val2>>6)?0:val1>>val2);
            }
            memory[ (code[i]>>56)&1 ? memory[p3] : p3 ] = val3;
        }
        else if(op==5)  //Calculate (+ - * / %)
        {
            //想要乘方的建议自己写一个快速幂, 应该是能写的 
            int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535;
            int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ],
            val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ], val3;
            int op2 = (code[i]>>52)&15;
            if(op2==0)
            {
                val3=val1+val2;
            }
            else if(op2==1)
            {
                val3=val1-val2;
            }
            else if(op2==2)
            {
                val3=val1*val2;
            }
            else if(op2==3)
            {
                val3=(val2?val1/val2:0);
            }
            else
            {
                val3=(val2?val1%val2:0);
            }
            memory[ (code[i]>>56)&1 ? memory[p3] : p3 ] = val3;
        }
        else if(op==6)  //Goto
        {
            int p=code[i]&65535;
            i = (code[i]>>56)&1 ? memory[p] : p;
            i = (i+N-1)%N;
        }
        else if(op==7)  //If-goto (> < == >= <= !=)
        {
            int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535;
            int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ],
            val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ];
            int op2 = (code[i]>>52)&15;
            bool flag;
            if(op2==0)
            {
                flag=(val1>val2);
            }
            else if(op2==1)
            {
                flag=(val1<val2);
            }
            else if(op2==2)
            {
                flag=(val1==val2);
            }
            else if(op2==3)
            {
                flag=(val1>=val2);
            }
            else if(op2==4)
            {
                flag=(val1<=val2);
            }
            else
            {
                flag=(val1!=val2);
            }
            if(flag)
            {
                i = (code[i]>>56)&1 ? memory[p3] : p3;
                i = (i+N-1)%N;
            }
        }
        else if(op==8)  //x++
        {
            int p=code[i]&65535;
            memory[ (code[i]>>56)&1 ? memory[p] : p ]++;
        }
        else if(op==9)  //x--
        {
            int p=code[i]&65535;
            memory[ (code[i]>>56)&1 ? memory[p] : p ]--;
        }
        else if(op==15) //Exit
        {
            break;
        }
        else
        {
            cout<<"\n\nError: Invalid code\n\n";
        }
    }
    return 0;
}

程序解释

将 code 数组设为 0x0000000000000000, 0x0000000000000001, 0x5000000000010002, 0x1000000000000002, 0xf000000000000000 即可达到 A+B Problem 的要求。逐行解析：

0x0000000000000000：输入一个整数，将其存放于内存的 0 号位置；
0x0000000000000001：输入一个整数，将其存放于内存的 1 号位置；
0x5000000000010002：将内存的 0,1 号位置的数相加，并将结果存放在内存的 2 号位置；
0x1000000000000002：将 2 号位置的数以数字形式输出；
0xf000000000000000：退出程序。

附赠一些其它的常用程序：

Hello world：

// 将其复制进代码的第 8 行即可
0x2000000000000048, 0x1200000000000000, //H
0x2000000000000065, 0x1200000000000000, //e
0x200000000000006c, 0x1200000000000000, //l
0x200000000000006c, 0x1200000000000000, //l
0x200000000000006f, 0x1200000000000000, //o
0x200000000000002c, 0x1200000000000000, //,
0x2000000000000020, 0x1200000000000000, //[Space]
0x2000000000000077, 0x1200000000000000, //w
0x200000000000006f, 0x1200000000000000, //o
0x2000000000000072, 0x1200000000000000, //r
0x200000000000006c, 0x1200000000000000, //l
0x2000000000000064, 0x1200000000000000, //d
0x2000000000000021, 0x1200000000000000, //!
0x200000000000000a, 0x1200000000000000, //[\n]
0xf000000000000000  //exit

解析：将 0 号位置依次设为 Hello, world! 中每个字符的 ASCII 码并将其以字符形式输出。

输出 0\sim n-1：

// 将其复制进代码的第 8 行即可
0x0000000000000000, 0x2000000100000020,
0x7030000200000007, 0x1000000000000002,
0x1200000000000001, 0x8000000000000002,
0x6000000000000002, 0xf000000000000000

逐行解析：

0x0000000000000000：输入一个整数，将其存放于内存的 0 号位置；
0x2000000100000020：将内存 1 号位置的值设为 32（\text{0x20}，即空格的 ASCII 码）；
0x7030000200000007：如果内存的 0,2 号位置的值相等，则跳转至第 7 行代码（即 0xf000000000000000）；
0x1000000000000002：以数字形式输出内存 2 号位置的值；
0x1200000000000001：以字符形式输出内存 1 号位置的值；
0x8000000000000002：将 2 号位置的值加 1；
0x6000000000000002：跳转至第 2 行代码（即 0x7030000200000007）；
0xf000000000000000：退出程序。

Part II：64 位 8\text{MB} 内存的汇编虚拟机

我们又注意到，这道题还可以通过手搓一个拥有 8\text{MB} 内存、64 位系统、使用类似汇编的语言的虚拟机来完成。

AC 记录：link。

代码实现

Code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned int
#define N 1048576
int memory[N],pos;
string code[N]={

};
string readStr(int x,int y) // 从 code[x][y] 开始读取一个字符串, 读到空格为止 
{
    pos=y;
    string ret="";
    int len=code[x].length();
    while(pos<len && code[x][pos]==' ')
    {
        ++pos;
    }
    while(pos<len && code[x][pos]!=' ')
    {
        ret=ret+code[x][pos++];
    }
    return ret;
}
int readInt(int x,int y)    // 从 code[x][y] 开始读取一个整数, 读到非数字为止 
{
    pos=y;
    int ret=0, len=code[x].length();
    bool f=0;
    while(pos<len && !isdigit(code[x][pos]))
    {
        if(code[x][pos]=='-')
        {
            f=1;
        }
        ++pos;
    }
    while(pos<len && isdigit(code[x][pos]))
    {
        ret=(ret<<3)+(ret<<1)+(code[x][pos++]^48);
    }
    return f?-ret:ret;
}
signed main()
{
    for(int i=0;;i=(i+1)%N)
    {
        string op=readStr(i,0);
        if(op=="input")
        {
            int x=readInt(i,pos);
            cin>>memory[x];
        }
        else if(op=="output")
        {
            string mode=readStr(i,pos);
            if(mode=="int")
            {
                int x=readInt(i,pos);
                cout<<memory[x];
            }
            else if(mode=="char")
            {
                int x=readInt(i,pos);
                cout<<char(memory[x]%128);
            }
            else
            {
                cout<<"\n\nError: Invalid Code at i = "<<i<<"\n\n";
                break;
            }
        }
        else if(op=="write")
        {
            int x=readInt(i,pos), y=readInt(i,pos);
            memory[x]=y;
        }
        else if(op=="copy")
        {
            int x=readInt(i,pos), y=readInt(i,pos);
            memory[y]=memory[x];
        }
        else if(op=="calc") // and or not xor add sub mul div mod
        {
            string mode=readStr(i,pos);
            int x=readInt(i,pos), y=readInt(i,pos), z=(mode=="not" ? 0 : readInt(i,pos));
            x=memory[x], y=memory[y];
            if(mode=="and")
            {
                memory[z]=x&y;
            }
            else if(mode=="or")
            {
                memory[z]=x|y;
            }
            else if(mode=="not")
            {
                memory[y]=~x;
            }
            else if(mode=="xor")
            {
                memory[z]=x^y;
            }
            else if(mode=="add")
            {
                memory[z]=x+y;
            }
            else if(mode=="sub")
            {
                memory[z]=x-y;
            }
            else if(mode=="mul")
            {
                memory[z]=x*y;
            }
            else if(mode=="div")
            {
                if(y==0)
                {
                    cout<<"\n\nError: Division by Zero\n\n";
                    break;
                }
                memory[z]=x/y;
            }
            else if(mode=="mod")
            {
                memory[z]=x%y;
            }
            else
            {
                cout<<"\n\nError: Invalid Code at i = "<<i<<"\n\n";
                break;
            }
        }
        else if(op=="goto")
        {
            int x=readInt(i,pos);
            i=x-1;
        }
        else if(op=="if")   // < > == <= >= !=
        {
            string mode=readStr(i,pos);
            int x=readInt(i,pos), y=readInt(i,pos), z=readInt(i,pos);
            x=memory[x], y=memory[y];
            if(mode=="<")
            {
                if(x<y)
                {
                    i=z-1;
                }
            }
            else if(mode==">")
            {
                if(x>y)
                {
                    i=z-1;
                }
            }
            else if(mode=="==")
            {
                if(x==y)
                {
                    i=z-1;
                }
            }
            else if(mode=="<=")
            {
                if(x<=y)
                {
                    i=z-1;
                }
            }
            else if(mode==">=")
            {
                if(x>=y)
                {
                    i=z-1;
                }
            }
            else if(mode=="!=")
            {
                if(x!=y)
                {
                    i=z-1;
                }
            }
            else
            {
                cout<<"\n\nError: Invalid Code at i = "<<i<<"\n\n";
                break;
            }
        }
        else if(op=="++")
        {
            int x=readInt(i,pos);
            memory[x]++;
        }
        else if(op=="--")
        {
            int x=readInt(i,pos);
            memory[x]--;
        }
        else if(op=="exit")
        {
            break;
        }
        else
        {
            cout<<"\n\nError: Invalid Code at i = "<<i<<"\n\n";
            break;
        }
    }
    return 0;
}

程序解释

对其中每种指令的介绍（{} 表示必选参数，[] 表示可选参数）：

input {x}：输入一个整数（范围：[-2^{63},2^{63})），并将其存放于内存的 x 号位置。
output {mode} {x}：以 mode 形式（int 或 char，其中 char 形式是按照 ASCII 码输出）输出内存的 x 号位置中的数据。
write {x} {y}：将内存的 x 号位置的数据设为 y。
copy {x} {y}：将内存的 x 号位置的数据拷贝至内存的 y 号位置。
calc {mode} {x} {y} [z]（当 mode 为 not 时无需 z）：将内存的 x 号位置的数据与内存的 y 号位置的数据进行 mode 运算（and、or、xor、add、sub、mul、div 或 mod，其中 div 操作在除数为 0 时会提示 Error: Division by Zero 并退出程序），并将结果存放在内存的 z 号位置。

注：当 mode 为 not 时，其效果为将内存的 x 号位置的数据按位取反的结果存放在内存的 y 号位置；此处的 and、or、xor 和 not 均为位运算，逻辑运算是可以通过这个实现的，故没有单独制作。
goto {x}：跳转至第 x 行（从 0 开始）代码。
if {mode} {x} {y} {z}：如果内存的 x,y 号位置的数据满足 mode 这一关系（mode 可在 <、>、==、<=、>= 和 != 中选择），则跳转至第 z 行（从 0 开始）代码。
++ {x}：将内存的 x 号位置的数据加 1。
-- {x}：将内存的 x 号位置的数据减 1。
exit：退出程序。

此外，如果在运行过程中发现了无效的代码，则会提示 Error: Invalid Code 并直接退出程序。

将 code 数组设为 "input 0", "input 1", "calc add 0 1 2", "output int 2", "exit" 即可实现 A+B Problem 的要求。

附赠若干程序（将其复制进程序的第 8 行即可）：

Hello world：

"write 0 72", "output char 0",
"write 0 101", "output char 0",
"write 0 108", "output char 0",
"write 0 108", "output char 0",
"write 0 111", "output char 0",
"write 0 44", "output char 0",
"write 0 32", "output char 0",
"write 0 119", "output char 0",
"write 0 111", "output char 0",
"write 0 114", "output char 0",
"write 0 108", "output char 0",
"write 0 100", "output char 0",
"write 0 33", "output char 0",
"exit"

解析：显然。

输出 0\sim n-1：

"input 0",
"write 2 32",
"if == 0 1 7",
"output int 1",
"output char 2",
"++ 1",
"goto 2",
"exit"

逐行解析：

input 0：输入一个整数，将其存放于内存的 0 号位置；
write 2 32：将内存 2 号位置的值设为 32（即空格的 ASCII 码）；
if == 0 1 7：如果内存的 0,1 号位置的值相等，则跳转至第 7 行代码（即 exit）；
output int 1：以数字形式输出内存 1 号位置的值；
output char 2：以字符形式输出内存 2 号位置的值；
++ 1：将 1 号位置的值加 1；
goto 2：跳转至第 2 行代码（即 if == 0 1 7）；
exit：退出程序。

P1226 【模板】快速幂（AC 记录：link）：

// 输入 & 预处理 
"input 0", "input 1",
"input 2", "write 3 1",
"copy 0 4", "copy 1 5",
"write 7 1", "write 8 2",
// 计算 
"if == 5 6 17", "calc and 5 7 9",
"if == 9 6 13", "calc mul 3 4 3",
"calc mod 3 2 3", "calc div 5 8 5",
"calc mul 4 4 4", "calc mod 4 2 4",
"goto 8",
// 输出 
"output int 0", "write 10 94",
"output char 10", "output int 1",
"write 11 32", "output char 11",
"write 10 109", "output char 10",
"write 10 111", "output char 10",
"write 10 100", "output char 10",
"output char 11", "output int 2",
"write 10 61", "output char 10",
"output int 3", "exit"

解析：基本相当于这段代码 ~~（绝对不是我懒得对这么长的代码写逐行解析了）~~：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,tmp,mod,ans=1,cnt=0,p;
int main()
{
    cin>>a>>b>>mod;
    p=a;
    tmp=b;
    while(tmp)
    {
        if(tmp&1)
        {
            ans*=p;
            ans%=mod;
        }
        tmp/=2;
        p*=p;
        p%=mod;
    }
    cout<<a<<"^"<<b<<" mod "<<mod<<"="<<ans;
    return 0;
}

欢迎各位大佬在评论区批评指正。