Don't like ads? PRO users don't see any ads ;-)
Guest

Untitled

By: a guest on Jun 17th, 2012  |  syntax: None  |  size: 3.42 KB  |  hits: 21  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5.  
  6. using namespace std;
  7.  
  8. class BigInteger
  9. {
  10.         char *str;
  11.         int len;
  12.  
  13.         public:
  14.  
  15.         BigInteger (char a[ ]) /* Constructor that Dynamically allocates memory to hold the number and
  16.         initializes the number with a[ ] and sets the length. */
  17.         {
  18.                 len=strlen(a);
  19.                 str=new char [len+1];
  20.  
  21.                 strcpy(str,a);
  22.         }
  23.  
  24.        
  25.         BigInteger( ) /*Default constructor that creates a big integer equivalent to zero. */
  26.         {
  27.                 len=1;
  28.                 str=new char[len+1];
  29.                 (*str)='0';
  30.         }
  31.          
  32.         BigInteger(const BigInteger &ob)
  33.         {
  34.        
  35.                 len=strlen(ob.str);
  36.  
  37.                 str=new char[len+1];
  38.  
  39.                 strcpy(str,ob.str);
  40.         }
  41.  
  42.         //assignment operator overloading
  43.         BigInteger &operator=(BigInteger ob)
  44.         {
  45.                 if(strlen(ob.str)>len)
  46.                 {
  47.                         /*if(str) */delete [] str;
  48.                         len=strlen(ob.str);
  49.                         str=new char[len+1];
  50.                         strcpy(str,ob.str);
  51.                 }
  52.  
  53.                 else
  54.                 {
  55.                         len=strlen(ob.str);
  56.                         strcpy(str,ob.str);
  57.                 }
  58.  
  59.                 return *this;
  60.         }
  61.  
  62.  
  63.         ~BigInteger ( )  /*Destructor that frees memory. */
  64.         {
  65.                 delete [] str;
  66.         }
  67.  
  68.         void SetBigInteger(char a[ ] )  /* This function is like the first constructor that the number with a[ ]
  69.         and sets the Length.  */
  70.         {
  71.                 if(strlen(a)>len)
  72.                 {
  73.                         delete [] str;
  74.                         len=strlen(a);
  75.                         str=new char[len+1];
  76.                         strcpy(str,a);
  77.                 }
  78.  
  79.                 else
  80.                 {
  81.                         len=strlen(a);
  82.                         strcpy(str,a);
  83.                 }
  84.  
  85.         }
  86.  
  87.         BigInteger Multiply(BigInteger n)  /* Multiplies big integer n with current object and returns the
  88.         result, without affecting the current object.  */
  89.         {
  90.                 BigInteger res;
  91.                 res.len=len+n.len;
  92.                 res.str=new char[res.len+1];
  93.                
  94.                 memset(res.str,'0',res.len);
  95.  
  96.                 int i,j,k,carry=0,count=0,cnt,track=res.len-1;
  97.  
  98.                 char **arr;
  99.  
  100.                 arr=new char*[n.len];
  101.  
  102.                 for(i=0;i<n.len;i++)
  103.                 {
  104.                         arr[i]=new char [res.len];
  105.                 }
  106.  
  107.                 for(i=n.len-1;i>=0;i--)
  108.                 {
  109.                         cnt=count;
  110.                         track=res.len-1-count;
  111.                        
  112.                         for(j=res.len-1;cnt>0;cnt--,j--)
  113.                         {
  114.                                 arr[n.len-i-1][j]='0';
  115.                         }
  116.                        
  117.                         for(j=len-1;j>=0;j--)
  118.                         {
  119.                                 arr[n.len-i-1][track]=(str[j]-'0')*(n.str[i]-'0')+carry;
  120.                                
  121.                                 if((int)arr[n.len-i-1][track]>9)
  122.                                 {
  123.                                         carry=(arr[n.len-i-1][track])/10;
  124.                                         arr[n.len-i-1][track]=(((int)arr[n.len-i-1][track])%10)+'0';
  125.                                 }
  126.  
  127.                                 else
  128.                                 {
  129.                                         carry=0;
  130.                                         arr[n.len-i-1][track]=(((int)arr[n.len-i-1][track]))+'0';
  131.                                 }
  132.                                
  133.                                 track--;
  134.                         }
  135.  
  136.                         for(j=track;j>=0;j--)
  137.                         {
  138.                                 arr[n.len-i-1][j]=carry+'0';
  139.  
  140.                                 if(arr[n.len-i-1][track]>'9')
  141.                                 {
  142.                                         carry=(arr[n.len-i-1][track]-'0')/10;
  143.                                         arr[n.len-i-1][track]=((arr[n.len-i-1][track]-'0')%10)+'0';
  144.                                 }
  145.  
  146.                                 else carry=0;
  147.                         }
  148.  
  149.                         count++;
  150.                 }
  151.                
  152.                 carry=0;
  153.                
  154.                 //final answer
  155.                 for(i=res.len-1;i>=0;i--)
  156.                 {
  157.                         for(j=0;j<n.len;j++)
  158.                         {
  159.                                 res.str[i]+=arr[j][i]+carry-'0';
  160.                                 carry=0;
  161.                         }
  162.                        
  163.                         if(res.str[i]>'9')
  164.                                 {
  165.                                         carry=(res.str[i]-'0')/10;
  166.                                         res.str[i]=((res.str[i]-'0')%10)+'0';
  167.                                 }
  168.  
  169.                                 else carry=0;
  170.                 }
  171.                
  172.                 res.str[res.len]='\0';
  173.  
  174.                 return res;
  175.         }
  176.  
  177.         void Show( )/* Prints the big integer on screen.  */
  178.         {
  179.                 char *p;
  180.  
  181.                 p=str;
  182.  
  183.                 while((*p)=='0')
  184.                 {
  185.                         p++;
  186.                 }
  187.  
  188.                 cout<<p<<endl;
  189.         }
  190.  
  191. };
  192.  
  193. int main()
  194. {
  195.         char s1[500],s2[500];
  196.         BigInteger a,b,res;
  197.        
  198.         while(( scanf("%s%s",s1,s2) )!=EOF)
  199.         {
  200.                 a.SetBigInteger(s1);
  201.                 b.SetBigInteger(s2);
  202.  
  203.                 if(s1[0]=='0' || s2[0]=='0')
  204.                 {
  205.                         cout<<"0"<<endl;
  206.                 }
  207.  
  208.                 else
  209.                 {
  210.                         res=a.Multiply(b);
  211.                         res.Show();
  212.                 }
  213.  
  214.                 memset(s1,'\0',500);
  215.                 memset(s2,'\0',500);
  216.         }
  217.        
  218.         return 0;
  219. }