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
6int 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
20void 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
36void 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
44int 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
5using namespace std;
6
7#define L 1002
8#define LIM 500
9
10typedef int BI[ L ];
11BI buf[ LIM ];
12int top;
13
14#define bi_copy(a,b) memcpy( (void*)(a), (void*)(b), sizeof(int)*L )
15
16void 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
26void 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
37void 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
64void 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
79void 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
91void 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
154int 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