e931 - pA. 直式乘法
題目描述
題目要求模擬直式乘法的過程，給定兩個正整數 a 和 b，輸出類似手算乘法的格式，包含被乘數、乘數、分隔線以及中間結果的加總。
解題思路
程式碼的核心思想是模擬直式乘法的步驟。首先，計算 a 和 b 的乘積，並確定輸出格式的寬度（l），寬度取決於乘積、被乘數和乘數的位數的最大值。然後，程式碼按照直式乘法的格式輸出被乘數、乘數、分隔線。接著，程式碼迭代乘數的每一位，計算每一位與被乘數的乘積，並在適當的位置輸出。最後，輸出分隔線和最終的乘積。程式碼使用迴圈和空格來調整輸出格式，以確保對齊。
複雜度分析
- 時間複雜度: O(len(a) * len(b))，其中 len(a) 和 len(b) 分別是被乘數和乘數的位數。這是因為程式碼需要迭代乘數的每一位，並計算每一位與被乘數的乘積。
- 空間複雜度: O(1)，程式碼使用的額外空間是常數級別的，主要用於儲存變數，例如 a、b、l 等。
程式碼
#include <iostream>
using namespace std;
int a,b;
int w(int tmp){
int k=1;
while(tmp/=10){
++k;
}
return k;
}
int main(){
cin >> a >> b;
int l=w(a*b),al=w(a),bl=w(b),ab=a*b;
l=max(l,max(al,bl));
int t=l-al;
while(t){
--t;
cout << " ";
}
cout << a << "\n";
t=l-bl;
while(t){
--t;
cout << " ";
}
cout << b << "\n";
t=l;
while(t){
--t;
cout << "-";
}
cout << "\n";
t=bl;
for(int i=0;i<t;++i){
int ks=b%10;
b/=10;
int tt=l-w(ks*a)-i;
while(tt){
--tt;
cout << " ";
}
cout << ks*a ;
int ii=i;
while(ii){
--ii;
cout << " ";
}
cout << "\n";
}
t=l;
while(t){
--t;
cout << "-";
}
cout << "\n";
cout << ab;
}