- POJ 2389 - Bull Math
- Time: 1000MS
- Memory: 10000K
- 难度: 初级
- 分类: 高精度算法
0x00 POJ 原题
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
1111111111Sample Output
12345679011110987654321Source
0x10 解题思路
大数相乘，水题一道，直接模拟笔算竖式即可，没技巧没算法。
0x20 AC 源码
//Memory Time
//216K 16MS
#include<iostream>
#include<string>
using namespace std;
const int size=1000; //大数位数
void mult(char* A,char* B,char* ans)
{
int a[size+1]={0};
int b[size+1]={0};
int pa=0,pb=0;
int c[2*size+1]={0};
int lena=strlen(A);
int lenb=strlen(B);
for(int i=lena-1;i>=0;i--)
a[pa++]=A[i]-'0';
for(int j=lenb-1;j>=0;j--)
b[pb++]=B[j]-'0';
for(pb=0;pb<lenb;pb++)
{
int w=0; //低位到高位的进位
for(pa=0;pa<=lena;pa++)
{
int temp=a[pa]*b[pb]+w;
w=temp/10;
temp=(c[pa+pb]+=temp%10);
c[pa+pb]=temp%10;
w+=temp/10;
}
}
bool flag=false;
bool sign=false; //标记ans是否为全0
for(pa=0,pb=lena+lenb-1;pb>=0;pb--)
{
if(!flag && c[pb]==0) //删除ans开头的0
continue;
else
flag=true;
sign=true;
ans[pa++]=c[pb]+'0';
}
if(sign)
ans[pa]='\0';
else
{
ans[0]='0';
ans[1]='\0';
}
return;
}
int main(void)
{
char a[size+1];
char b[size+1];
char ans[2*size+1];
while(cin>>a>>b)
{
mult(a,b,ans);
cout<<ans<<endl;
}
return 0;
}
