Description
Bulls are so much better at math than the cows. They can multiply huge integers together and get perfectly precise answers ... or so they say. Farmer John wonders if their answers are correct. Help him check the bulls' answers. Read in two positive integers (no more than 40 digits each) and compute their product. Output it as a normal number (with no extra leading zeros).
FJ asks that you do this yourself; don't use a special library function for the multiplication.
Input
* Lines 1..2: Each line contains a single decimal number.
Output
* Line 1: The exact product of the two input lines
Sample Input
11111111111111
1111111111 Sample Output
12345679011110987654321 題目大意：
輸入兩行，每行一個整數，計算兩整數的積。（注意前導零的情況）
解題思路：
高精度的乘法，将兩個或多個數以字元串的形式儲存在數組中，然後将字元串數組翻轉并轉化為對應的整形數組，然後用一個數組的每一位去乘另一數組的每一位，累加每一位，最後做進位操作，倒着輸出數組即可。
舉例說明：1678278312397215與719290058710108相乘
第一步：字元串數組儲存
字元數組：s1[ ]：
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
s1[ ] 1 6 7 8 2 7 8 3 1 2 3 9 7 2 1 5
s2[ ]：
j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
s2[ ] 7 1 9 2 9 0 0 5 8 7 1 0 1 0 8
第二步：轉化為整形數組并翻轉數組（注意去除前導0）
整形數組：a1[ ]：
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a1[ ] 5 1 2 7 9 3 2 1 3 8 7 2 8 7 6 1
a2[ ]：
j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
a2[ ] 8 0 1 0 1 7 8 5 0 0 9 2 9 1 7
第三步：計算每一位的乘積并累加
i=0，j從0到最大（在這裡是14）
計算每一位的乘積：num[i+j]=a1[i]*a2[j]
k=i+j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
num[ ] 40 0 5 0 5 35 40 25 0 0 45 10 45 5 35
累加每一位的和：sum[k]=sum[k]+num[k]
k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
num[ ] 40 0 5 0 5 35 40 25 0 0 45 10 45 5 35
舊sum[ ] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
新sum[ ] 40 0 5 0 5 35 40 25 0 0 45 10 45 5 35
i=1，j從0到最大
計算每一位的乘積：num[i+j]=a1[i]*a2[j]
k=i+j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
num[ ] 8 0 1 0 1 7 8 5 0 0 9 2 9 1 7
累加每一位的和：sum[k]=sum[k]+num[k]
k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
num[ ] 8 0 1 0 1 7 8 5 0 0 9 2 9 1 7
舊sum[ ] 40 0 5 0 5 35 40 25 0 0 45 10 45 5 35
新sum[ ] 48 0 6 0 6 42 48 30 0 0 54 12 54 6 42
…… …… …… ……
…… …… …… ……
i最大（這裡是15），j從0到最大
計算每一位的乘積：num[i+j]=a1[i]*a2[j]
k=i+j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
num[ ] 8 0 1 0 1 7 8 5 0 0 9 2 9 1 7
累加每一位的和：sum[k]=sum[k]+num[k]
k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ……
num[ ] 8 0 1 0 1 7 8 5 0 0 9 2 9 1 7 ……
舊sum[ ] …… …… …… …… ……
新sum[ ] …… …… …… …… ……
第四步：進位操作，将數組的每一位化為小于10的整數
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
sum 40 8 21 57 79 67 74 65 105 197 234 127 177 186 297 262 250 213 242 249 211 152 173 160 191 106 119 64 43 7 0
sum 0 2 2 9 4 5 1 3 2 8 4 2 2 5 7 3 9 0 6 5 8 5 0 9 8 6 1 7 0 2 1
第五步：倒着輸出數組sum即可。
sum：1207168905856093752248231549220
代碼如下：
#include<stdio.h>
#include<string.h>
int main()
{
/*num:記錄進位的數值；sum數組：開始時儲存各個位的和，後來儲存進位後各個位的數字；
sum1數組記錄将字元str1轉換的整數；sum2數組記錄将字元str2轉換的整數；*/
int i,j,k,n,p,q,num,sum[90]={0},sum1[45],sum2[45];
char str1[45],str2[45];
//對字元串1的操作
scanf("%s",str1);
for(i=0;str1[i]=='0';i++);//去除前導0
n=strlen(str1);//測量字元串1的長度
for(j=n-1,k=0;j>=i;j--,k++)//将字元串的各個位的字元轉化為數字，循環次數隻需n-i次
sum1[k]=str1[j]-'0';
p=k;//記錄整數1的位數
//對字元串2的操作
scanf("%s",str2);
for(i=0;str2[i]=='0';i++);//去除前導0
n=strlen(str2);//測量字元串2的長度
for(j=n-1,k=0;j>=i;j--,k++)//将字元串的各個位的字元轉化為數字，循環次數隻需n-i次
sum2[k]=str2[j]-'0';
q=k;//記錄整數2的位數
//循環，将兩整數的任意一位相乘，并累加相應位上的和，此時的和未進行進位操作
for(i=0;i<p;i++)
{
for(j=0;j<q;j++)
{
sum[i+j]=sum[i+j]+sum1[i]*sum2[j];
}
}
//對sum數組的每一位進行進位操作，得到兩數相乘的積的各個位的數字
for(i=0;i<p+q;i++)
{
if(sum[i]>9)
{
num=sum[i]/10;
sum[i]=sum[i]%10;
sum[i+1]=sum[i+1]+num;
}
}
//從sum數組的右端開始找，兩數相乘結果的最高位
for(i=p+q;sum[i]==0;i--);
//倒着輸出sum數組即是兩數相乘的積
for(j=i;j>=0;j--)
printf("%d",sum[j]);
printf("\n");
return 0;
}
![poj 1001（高精度）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)