duonglee

BCBIGNUM - Xử lý số nguyên lớn

Jun 26th, 2017
527
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.71 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. int StrToNumArr (char a[], char b[], int A[], int B[]) {
  5.     int lenA = strlen (a);
  6.     int lenB = strlen (b);
  7.    
  8.     int len;
  9.     if (lenA>lenB) len=lenA;
  10.     else len = lenB;
  11.    
  12.     lenA--;
  13.     lenB--;
  14.     for (int i=len-1; i>=0; i--) {
  15.         if (lenA>=0) {
  16.             A[i] = a[lenA]-'0';
  17.             lenA--;
  18.         } else A[i]=0;
  19.        
  20.         if (lenB>=0) {
  21.             B[i] = b[lenB]-'0';
  22.             lenB--;
  23.         } else B[i]=0;
  24.     }
  25.     return len;
  26. }
  27.  
  28. int SumBig (int A[], int B[], int len, int C[]) {
  29.     for (int i=len-1; i>=0; i--) {
  30.         if (i!=0) {
  31.             int x = A[i]+B[i];
  32.             C[i]=x%10;
  33.             B[i-1]=B[i-1]+(x/10);
  34.         } else C[i]=A[i]+B[i];
  35.     }
  36.     return len;
  37. }
  38.  
  39. int ss (int A[], int B[], int len) {
  40.     for (int i=0; i<len; i++) {
  41.         if (A[i]>B[i]) return 1;
  42.         else if (A[i]<B[i]) return -1;
  43.     }
  44.     return 0;
  45. }
  46.  
  47. int MiBig (int A[], int B[], int len, int C[], int *dau) {
  48.     int hs=ss (A, B, len);
  49.     if (hs==0) return 0;
  50.     *dau=hs;
  51.     for (int i=len-1; i>=0; i--) {
  52.         int x;
  53.         if (hs==1) x=A[i]-B[i];
  54.         else x=B[i]-A[i];
  55.         if (i!=0) {
  56.             if (x>=0) C[i]=x;
  57.             else {
  58.                 C[i]=x+10;
  59.                 if (hs==1) B[i-1]=B[i-1]+1;
  60.                 else A[i-1]=A[i-1]+1;
  61.             }
  62.         } else {
  63.             C[i]=x;
  64.         }
  65.     }
  66.     for (int i=0; i<len; i++) {
  67.         if (C[i]!=0) return (len-i);
  68.     }
  69. }
  70.  
  71. void sc (int A[], int B[], int len) {
  72.     // Cop B -> A;
  73.     for (int i=0; i<len; i++) {
  74.         A[i]=B[i];
  75.     }
  76. }
  77.  
  78. int PrBig (int A[], int B[], int len, int C[]) {
  79.     int Btg[2006];
  80.     int Ctg[2006];
  81.     int lenMax=2*len;
  82.     for (int i=0; i<lenMax; i++) {
  83.         Btg[i]=0;
  84.         Ctg[i]=0;
  85.     }
  86.     for (int i=len-1; i>=0; i--) {
  87.         lenMax--;
  88.         int k=lenMax;
  89.         for (int j=0; j<2*len; j++) {
  90.             Btg[j]=0;
  91.         }
  92.         for (int j=len-1; j>=0; j--) {
  93.             int x=Btg[k]+B[i]*A[j];
  94.             Btg[k]=(x)%10;
  95.             Btg[k-1]=(x)/10;
  96.             k--;
  97.         }
  98.         SumBig (Ctg, Btg, 2*len, C);
  99.         sc (Ctg, C, 2*len);
  100.     }
  101.     for (int i=0; i<2*len; i++) {
  102.         if (C[i]!=0) return (2*len-i);
  103.     }
  104.     return 0;
  105. }
  106.  
  107. int main () {
  108.     char a[1001] = "";
  109.     char b[1001] = "";
  110.     scanf ("%s%s", a, b);
  111.     int len;
  112.    
  113.    
  114.    
  115.     int As[1003];
  116.     int Bs[1003];
  117.     int Sum[1003];
  118.     len = StrToNumArr (a, b, As, Bs);
  119.     int lenSum = SumBig (As, Bs, len, Sum);
  120.     for (int i=0; i<lenSum; i++) {
  121.         printf ("%d", Sum[i]);
  122.     }
  123.     printf ("\n");
  124.    
  125.     int Am[1003];
  126.     int Bm[1003];
  127.     len = StrToNumArr (a, b, Am, Bm);
  128.     int Mi[1003];
  129.     int dau=1;
  130.     int lenMi = MiBig (Am, Bm, len, Mi, &dau);
  131.     if (lenMi==0) printf ("0");
  132.     else {
  133.         if (dau==-1) printf ("-");
  134.         for (int i=len-lenMi; i<len; i++) {
  135.             printf ("%d", Mi[i]);
  136.         }
  137.     }
  138.     printf ("\n");
  139.    
  140.     int Ap[1003];
  141.     int Bp[1003];
  142.     len = StrToNumArr (a, b, Ap, Bp);
  143.     int Pr[2006];
  144.     int lenPr = PrBig (Ap, Bp, len, Pr);
  145.     if (lenPr==0) printf ("0");
  146.     else {
  147.         for (int i=2*len-lenPr; i<2*len; i++) {
  148.             printf ("%d", Pr[i]);
  149.         }
  150.     }
  151.    
  152.     return 0;
  153. }
Advertisement
Add Comment
Please, Sign In to add comment