Advertisement
cmiN

MUL

Apr 25th, 2011
276
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.78 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cctype>
  3.  
  4. int first[10010], second[10010], last[20010];
  5.  
  6. inline void read()
  7. {
  8.     first[0] = second[0] = last[0] = 0;
  9.     int min, i, temp;
  10.     char c;
  11.     while (!isspace(c = getchar())) {
  12.         first[++first[0]] = c - '0';
  13.     }
  14.     while (!(isspace(c = getchar()) || c == EOF)) {
  15.         second[++second[0]] = c - '0';
  16.     }
  17.     min = (first[0] < second[0] ? first[0] : second[0]) / 2;
  18.     for (i = 1; i <= min; ++i) {
  19.         temp = first[i];
  20.         first[i] = first[first[0] - i + 1];
  21.         first[first[0] - i + 1] = temp;
  22.         temp = second[i];
  23.         second[i] = second[second[0] - i + 1];
  24.         second[second[0] - i + 1] = temp;
  25.     }
  26.     while (i <= first[0] / 2) {
  27.         temp = first[i];
  28.         first[i] = first[first[0] - i + 1];
  29.         first[first[0] - i + 1] = temp;
  30.         ++i;
  31.     }
  32.     while (i <= second[0] / 2) {
  33.         temp = second[i];
  34.         second[i] = second[second[0] - i + 1];
  35.         second[second[0] - i + 1] = temp;
  36.         ++i;
  37.     }
  38. }
  39.  
  40. inline void write()
  41. {
  42.     for (int i = last[0]; i > 0; --i) {
  43.         putchar(last[i] + '0');
  44.     }
  45.     putchar('\n');
  46. }
  47.  
  48. void MultHuge(int* A, int* B, int* C)
  49. /* C <- A x B */
  50. { int i,j,T=0;
  51.   if ((A[0] == 1 && A[1] == 0) || (B[0] == 1 && B[1] == 0)) {
  52.       C[0] = 1;
  53.       C[1] = 0;
  54.       return;
  55.   }
  56.   C[0]=A[0]+B[0]-1;
  57.   for (i=1;i<=A[0]+B[0];) C[i++]=0;
  58.   for (i=1;i<=A[0];i++)
  59.     for (j=1;j<=B[0];j++)
  60.       C[i+j-1]+=A[i]*B[j];
  61.   for (i=1;i<=C[0];i++)
  62.     { T=(C[i]+=T)/10;
  63.       C[i]%=10;
  64.     }
  65.   if (T) C[++C[0]]=T;
  66. }
  67.  
  68. int main()
  69. {
  70.     //freopen("mul.in", "rt", stdin);
  71.     int nr;
  72.     scanf("%d\n", &nr);
  73.     while (nr-- > 0) {
  74.         read();
  75.         MultHuge(first, second, last);
  76.         write();
  77.     }
  78.     return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement