coreBugZJ

此 blog 已弃。

A X B 高精度乘法,分治(二分)加速——算法作业 2.2,EOJ 1070

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 
 8void input( int a[] ) {
 9        char s[ L ];
10        int len, i;
11        scanf( "%s", s );
12        len = strlen( s );
13        memset( a, 0sizeof(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, 0sizeof(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 

posted on 2011-03-28 19:41 coreBugZJ 阅读(560) 评论(0)  编辑 收藏 引用 所属分类: 课内作业


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理