Time Limit:1000MS Memory Limit:30000KB
Description
旺财的数学老师开始发威了,留了一道很大很大的整数之间乘法的问题。
Input
第1行有一个正整数N(0 < N < 11),表示有几组测试数据,接下来的2……N+1行里,每行有两个无正负号非负整数(都在500位以内),整数之间用一个空格
分开.
Output
输出每行非负整数的积,每个结果占一行。
Sample Input
3
1 1
100 200
12345678901234567890 1
Sample Output
1
20000
12345678901234567890
朴素的高精度乘法
1
#include <stdio.h>
2
#include <string.h>
3
4
#define L 1009
5
6
int a[ L ], b[ L ], c[ L ];
7
8
void input( int a[] )
{
9
char s[ L ];
10
int len, i;
11
scanf( "%s", s );
12
len = strlen( s );
13
memset( a, 0, sizeof(int)*L );
14
a[ 0 ] = len;
15
for ( i = 0; i < len; ++i )
{
16
a[ len - i ] = (int)(s[ i ] - '0');
17
}
18
}
19
20
void mul( int c[], int a[], int b[] )
{
21
int la = a[ 0 ], lb = b[ 0 ], i, j;
22
memset( c, 0, sizeof(int)*L );
23
for ( i = 1; i <= la; ++i )
{
24
for ( j = 1; j <= lb; ++j )
{
25
c[ i + j - 1 ] += a[ i ] * b[ j ];
26
c[ i + j ] += c[ i + j - 1 ] / 10;
27
c[ i + j - 1 ] %= 10;
28
}
29
}
30
c[ 0 ] = la + lb;
31
while ( (c[0]>1) && (c[c[0]]==0) )
{
32
--c[ 0 ];
33
}
34
}
35
36
void output( int a[] )
{
37
int i;
38
for ( i = a[ 0 ]; i >= 1; --i )
{
39
printf( "%d", a[ i ] );
40
}
41
printf( "\n" );
42
}
43
44
int main()
{
45
int td;
46
scanf( "%d", &td );
47
while ( td-- > 0 )
{
48
input( a );
49
input( b );
50
mul( c, a, b );
51
output( c );
52
}
53
return 0;
54
}
55
使用二分加速的高精度乘法
1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
5
using namespace std;
6
7
#define L 1002
8
#define LIM 500
9
10
typedef int BI[ L ];
11
BI buf[ LIM ];
12
int top;
13
14
#define bi_copy(a,b) memcpy( (void*)(a), (void*)(b), sizeof(int)*L )
15
16
void bi_out( int a[] )
{
17
char s[ L ];
18
int i;
19
for ( i = 0; i < a[0]; ++i )
{
20
s[ i ] = a[ a[0] - i ] + '0';
21
}
22
s[ a[0] ] = 0;
23
puts( s );
24
}
25
26
void bi_in( int a[] )
{
27
int len, i;
28
char s[ L ];
29
scanf( "%s", s );
30
len = strlen( s );
31
a[ 0 ] = len;
32
for ( i = 0; i < len; ++i )
{
33
a[ len - i ] = s[ i ] - '0';
34
}
35
}
36
37
void bi_add( int c[], int a[], int b[] )
{
38
int i, g = 0;
39
for ( i = 1; (i<=a[0])&&(i<=b[0]); ++i )
{
40
g += a[ i ] + b[ i ];
41
c[ i ] = g % 10;
42
g /= 10;
43
}
44
while ( i <= a[0] )
{
45
g += a[ i ];
46
c[ i ] = g % 10;
47
g /= 10;
48
++i;
49
}
50
while ( i <= b[ 0 ] )
{
51
g += b[ i ];
52
c[ i ] = g % 10;
53
g /= 10;
54
++i;
55
}
56
while ( g > 0 )
{
57
c[ i ] = g % 10;
58
g /= 10;
59
++i;
60
}
61
c[ 0 ] = i - 1;
62
}
63
64
void bi_shiftL( int a[], int n )
{
65
int i;
66
if ( n <= 0 )
{
67
return;
68
}
69
for ( i = a[0]; i >= 1; --i )
{
70
a[ i+n ] = a[ i ];
71
}
72
for ( i = 1; i <= n; ++i )
{
73
a[ i ] = 0;
74
}
75
a[ 0 ] += n;
76
}
77
78
// c[0] >= 2
79
void bi_half( int a[], int b[], int c[] )
{
80
int i;
81
b[ 0 ] = ( c[ 0 ] >> 1 );
82
for ( i = b[ 0 ]; i >= 1; --i )
{
83
b[ i ] = c[ i ];
84
}
85
a[ 0 ] = c[ 0 ] - b[ 0 ];
86
for ( i = a[ 0 ]; i >= 1; --i )
{
87
a[ i ] = c[ b[ 0 ] + i ];
88
}
89
}
90
91
void bi_mul( int c[], int a[], int b[] )
{
92
#define ADD(x) BI &x = buf[ top++ ]
93
#define ENTER ADD(w); ADD(x); ADD(y); ADD(z); ADD(r); ADD(s); ADD(t)
94
#define LEAVE top -= 7; return
95
#define MULONE( a, b ) { \
96
int i, x = a[ 1 ], g = 0; \
97
for ( i = 1; i <= b[ 0 ]; ++i )
{ \
98
g += b[ i ] * x; \
99
c[ i ] = g % 10; \
100
g /= 10; \
101
} \
102
while ( g > 0 )
{ \
103
c[ i++ ] = g % 10; \
104
g /= 10; \
105
} \
106
--i; \
107
while ( (i>1) && (c[i]==0) )
{ \
108
--i; \
109
} \
110
c[ 0 ] = i; \
111
}
112
113
if ( (a[0]<1) || (b[0]<1) )
{
114
return;
115
}
116
117
ENTER;
118
119
// for debug
120
if ( top >= LIM )
{
121
fprintf( stderr, "buf overflow" );
122
LEAVE;
123
}
124
125
if ( a[ 0 ] == 1 )
{
126
MULONE( a, b );
127
LEAVE;
128
}
129
if ( b[ 0 ] == 1 )
{
130
MULONE( b, a );
131
LEAVE;
132
}
133
bi_half( w, x, a );
134
bi_half( y, z, b );
135
bi_mul( r, w, y );
136
bi_shiftL( r, (a[0]>>1) + (b[0]>>1) );
137
bi_mul( s, z, w );
138
bi_shiftL( s, (a[0]>>1) );
139
bi_add( t, r, s );
140
bi_mul( r, x, y );
141
bi_shiftL( r, (b[0]>>1) );
142
bi_mul( s, x, z );
143
bi_add( c, t, r );
144
bi_add( t, c, s );
145
bi_copy( c, t );
146
LEAVE;
147
148
#undef ADD
149
#undef ENTER
150
#undef LEAVE
151
#undef MULONE
152
}
153
154
int main()
{
155
int td, a[ L ], b[ L ], c[ L ];
156
scanf( "%d", &td );
157
while ( td-- > 0 )
{
158
top = 0;
159
bi_in( a );
160
bi_in( b );
161
bi_mul( c, a, b );
162
bi_out( c );
163
}
164
return 0;
165
}
166
我的二分实现太挫了,加之这题数据规模太小,二分加速的反而慢一些,o(╯□╰)o