Занятие 16

Операции над длинными целыми числами

lint &operator+=(lint &a, const lint &b)
{ int p=0, i;
  if(a.size()<b.size())
    a.resize(b.size(),0);
  for(i=0; i<b.size(); ++i)
  { a[i]+=b[i]+p;
    if(a[i]>=lint_base)
    { a[i]-=lint_base;
      p=1;
    }
    else
      p=0;
  }
  for(; p && i<a.size(); ++i)
  { a[i]+=p;
    if(a[i]>=lint_base)
    { a[i]-=lint_base;
      p=1;
    }
    else
      p=0;
  }
  if(p>0)
    a.push_back(p);
  return a;
}
lint operator+(lint a, const lint &b)
{ return a+=b;
}

lint &operator*=(lint &a, int b) // 0<=b<100000
{ int p=0;
  if(b==0)
  {
    a.resize(1);
    a[0]=0;
  }
  else
  { for(int i=0; i<a.size(); ++i)
    { p+=a[i]*b;
      a[i]=p%lint_base;
      p/=lint_base;
    }
    while(p)
    { a.push_back(p%lint_base);
      p/=lint_base;
    }
  }
  return a;
}
lint operator*(lint a, int b) 
{ return a*=b;
}
lint operator*(int b, lint a) 
{ return a*=b;
}

lint operator*(const lint &a, const lint &b) 
{ lint r(1,0),t;
  for(int i=0; i<b.size(); ++i)
  { t=a*b[i];
    t.insert(t.begin(),i,0);
    r+=t;
  }
  return r;
}
lint &operator*=(lint &a, const lint &b) 
{ return a=a*b;
}

int ldiv(lint &a, int b) // 0<=b<100000, возвращается остаток
{ int p=0, i;
  for(i=a.size()-1; i>=0; --i)
  { p=p*lint_base+a[i];
    a[i]=p/b;
    p%=b;
  }
  for(i=a.size()-1; i>0 && a[i]==0; --i);
  a.resize(i+1);
  return p;
}
lint &operator/=(lint &a, int b) 
{ ldiv(a,b);
  return a;
}
lint operator/(lint a, int b) 
{ return a/=b;
}
int operator%(lint a, int b) 
{ return ldiv(a,b);
}