首页 > POJ题解 > POJ 2389 Bull Math C++版

POJ 2389 Bull Math C++版

2009年11月15日 13:06 Slyar 发表评论 阅读评论

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

高精度乘法

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

Slyar:就是高精度乘法，这次我尝试了直接把结果保存到字符串里返回，继续试验了不少字符串函数，很爽。注意结果里的前导0要去掉。过不去的试试 20 50 这个数据，或许会有收获，我在这WA了2次...

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
string bignum(string& a, string& b)
{
    int i, j, k;
    int sum[81] = {0};
    string c;
 
    /* 一位一位算乘法 */
    for (i = a.length() - 1; i >= 0; i--)
    {
        for (j = b.length() - 1; j >= 0; j--)
        {
            sum[i + j] += (a[i] - '0') * (b[j] - '0');
        }
    }
 
    /* 处理进位 */
    for (i = a.length() - 1; i >= 0; i--)
    {
        for (j = b.length() - 1; j >= 0; j--)
        {
            if (i + j == 0) break;
            sum[i + j - 1] += sum[i + j] / 10;
            sum[i + j] %= 10;
        }
    }
 
    /* 将数组转换为字符串 */
    for (i = 0; i < a.length() + b.length() - 1; i++)
    {
        if (sum[i] / 10)
        {
            c.append(1, (sum[i] / 10) + '0');
            c.append(1, (sum[i] % 10) + '0');
        }
        else
        {
            c.append(1, sum[i] + '0');
        }
    }
 
    /* 去掉前导0 */
    c.erase(0, c.find_first_not_of('0'));  
    if(c.empty()) c = "0";
 
    return c;
}
 
int main()
{
    int si, ci;
    string a, b, c;
    cin >> a >> b;
 
    c = bignum(a, b);
 
    cout << c << endl;
 
    //system("pause");
    return 0;
}
分类: POJ题解 标签: ,
  1. 本文目前尚无任何评论.

bnuep:0801010047