大数乘法

 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

#include<stdio.h>
#include<string.h>
#define N 202

int main() {
  int a[N] = {0}, b[N] = {0}, c[404] = {0}, la, lb, i, j,k, d = 0, n1, n2;//202 位数相乘，最长 404 位数
  int get(int *p);
  void change(int *a, int *b, int n);

  la = get(a);
  lb = get(b);
  n1 = la > lb ? la : lb;//较长的数长
  n2 = la < lb ? la : lb;//较短的数长

  if (la < lb)
    change(a, b, lb);

  //模拟乘法运算过程（进位等考虑）
  for (i = 0; i < n2; i++) {
    for (j = 0; j < n1; j++) {
      c[j + i] += (b[i] * a[j] + d)%10;
      d = (b[i] * a[j] + d) / 10;

      if (c[j+i]>9){
        d++;
        c[j+i]%=10;
      }
      if (a[j+1]==0&&d!=0){
        k=j+i+1;
        c[k]=d;
      }
    }
    d=0;
  }

  k=k>(j+i-2)?k:j+i-2;
  for (i = k; i >= 0; i--)//将倒序装入的结果打印
    printf("%d", c[i]);

  return 0;
}

//输入字符串作为数字，并返回数字去除前导 0 后的长度
int get(int *p) {
  char x[N];
  int l, i, ex = 0;

  scanf("%s", x);
  l = strlen(x);
  while (x[ex] == '0')
    ex++;
  for (i = ex; i < l; i++) //提取字符串数字到 int 数组，倒序排列
    *(p + l - i - 1) = x[i] - '0';
  return l - ex;
}


void change(int *a, int *b, int n) {
  int i, t;
  for (i = 0; i < n; i++) {
    t = a[i];
    a[i] = b[i];
    b[i] = t;
  }
}

1
2
3

1234567890123456789
98765432109876543210
121932631124517831023715309991126352690