Cod sursa(job #58612)

Utilizator crawlerPuni Andrei Paul crawler Data 6 mai 2007 16:04:51
Problema Next Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.69 kb
#include <stdio.h>
#include <vector>
#include <string>
#include <cmath>
#define base 1000000000
#define base2 ((ull) base * base)
#define KARATSUBA 111
#define fix(x) {x.resize(x[0]+3); x[x[0]+1]=x[x[0]+2]=0;}
#define ull unsigned long long

using namespace std;

class BigInt{
public:
      vector <unsigned> a;  //la final nu il las public
      int semn;         //merge si char dar asa un BigInt are 16 byte, alinierea e mai buna
      BigInt();
      BigInt(long long nr);   
      BigInt& operator+=(const BigInt &b);    //incrementare cu un alt numar mare
      BigInt& operator+=(long long k);        //incrementare cu orice intreg, in afara de unsigned long long > 2^63 (yeah, right)
      friend BigInt operator+(const BigInt &x, const BigInt &y);
      friend BigInt operator-(const BigInt &x, const BigInt &y);
      BigInt& operator*=(int k);
      friend BigInt operator*(const BigInt &x, const BigInt &y);
      friend BigInt operator/(const BigInt &x, const BigInt &y);
      friend BigInt operator%(const BigInt &x, const BigInt &y);
      BigInt& operator/=(int k);
      int operator%(int k);
      friend int operator==(const BigInt &x, const BigInt &y);
      friend int operator!=(const BigInt &x, const BigInt &y);
      friend int operator<(const BigInt &x, const BigInt &y);
      friend int operator<=(const BigInt &x, const BigInt &y);
      friend int operator>(const BigInt &x, const BigInt &y);
      friend int operator>=(const BigInt &x, const BigInt &y);
      void shr(unsigned k);
      void shl(unsigned k);
      void write(FILE *f) const;
      void read(FILE *f);
};

BigInt::BigInt()
{
       a.resize(4);
       a[0]=1;         
}

BigInt::BigInt(long long nr)
{
       if (nr<0) semn=-1, nr=-nr;
       unsigned long long k=nr;
       a.resize(1);
       a[0]=0;
       while (k>=base) a.push_back(k%base), k/=base;
       a.push_back(k);
       a[0]=a.size()-1;
       fix(a);
}

void BigInt::shr(unsigned k)
{
        if (k>a[0]) k=a[0];
        unsigned i;
        for (i=1; i<=a[0]-k; i++)
            a[i]=a[i+k];
        a[0]-=k;
        if (!a[0]) a[0]=1, a[1]=1;
        fix(a);
}

void BigInt::shl(unsigned k)
{
        unsigned i;
        a[0]+=k;
        a.resize(a[0]+2);
        for (i=a[0]; i>k; i--)
            a[i]=a[i-k];
        memset(&a[1], 0, 4*k);
}

BigInt& BigInt::operator+=(const BigInt &b)
{
     if (this == &b){       //in cazul ca in care fac a+=a;
        unsigned i, n=a[0]+1;
        if (n<=a.size()) a.resize(n+1);
        for (i=1; i<n; i++) 
            a[i]+=a[i];
        for (i=1; i<n; i++)
            if (a[i]>=base) a[i]-=base, a[i+1]++;
        if (a[n]) a[0]++;
        return *this;
     }
     unsigned i, n=b.a[0]+1;
     if (n>=a.size()) a.resize(n+1);
     for (i=1; i<n; ++i)
         if (a[i]+b.a[i]>=base) a[i]+=(b.a[i]-base), a[i+1]++; else a[i]+=b.a[i];
     if (a[n]) n++;
     if (n-1>a[0]) a[0]=n-1;
     fix(a);
     return *this;
}

BigInt operator+(const BigInt &x, const BigInt &y)
{
       BigInt rez;
       const unsigned *a, *b;
       if (x.a[0]>y.a[0]) a=&x.a[0], b=&y.a[0]; else a=&y.a[0], b=&x.a[0];       
       unsigned n=a[0]+1, m=b[0]+1;
       rez.a.resize(a[0]+2);
       memcpy(&rez.a[0], a, sizeof(unsigned) * (n+1));
       for (unsigned i=1; i<m; i++){
           rez.a[i]+=b[i];
           if (rez.a[i]>=base) rez.a[i]-=base, ++rez.a[i+1];
       }
       unsigned k=m;
       while (rez.a[k]>=base) rez.a[k]-=base, ++k, ++rez.a[k];
       if (rez.a[a[0]+1]) rez.a[0]++;
       fix(rez.a);
       return rez;
}

BigInt operator-(const BigInt &x, const BigInt &y)
{
       BigInt rez;            
       const unsigned *a = &x.a[0], *b = &y.a[0];
       unsigned n=a[0]+1, m=b[0]+1;
       rez.a.resize(a[0]+3);
       memcpy(&rez.a[0], a, sizeof(unsigned) * (n+1));
       for (unsigned i=1; i<m; i++){
           if (rez.a[i]>base) rez.a[i]+=base, --rez.a[i+1];
           rez.a[i]-=b[i];     //daca face underflow
           if (rez.a[i]>base) rez.a[i]+=base, --rez.a[i+1];
       }
       unsigned k=m;
       while (rez.a[k]>base) rez.a[k]+=base, ++k, --rez.a[k];
       while (!rez.a[rez.a[0]] && rez.a[0]>1) rez.a[0]--;
       fix(rez.a);
       return rez;
}

BigInt& BigInt::operator*=(int nr)
{
        if (nr<0) semn=-semn, nr=-nr;
        ull num, k=nr;
        unsigned i, n=a[0]+1;
        vector <unsigned> sol(a.size()+1);
        for (i=1; i<n; i++){
            num=a[i] * k;
            unsigned cat = num/base;
            sol[i]+=num - cat*(ull)base;
            sol[i+1]+=cat;   
            if (sol[i]>=base) sol[i]-=base, sol[i+1]++;
        }
        sol[0]=a[0];
        a=sol;
        if (a[a[0]+1]) a[0]++;
        while (a[0]>1 && !a[a[0]]) --a[0];
        fix(a);
        return *this;
}

BigInt operator%(const BigInt &x, const BigInt &y)
{
       if (x<y) return x;
       unsigned n=x.a[0], m=y.a[0];
       const unsigned *a=&x.a[0];
       BigInt nr=0, cat;
       nr.a.resize(m+4);
       unsigned i,j;
       for (i=n; i>0; i--){
           nr.a[0]++;
           for (j=nr.a[0]; j>1; j--)
               nr.a[j]=nr.a[j-1];
           nr.a[1]=a[i];
           while (nr.a[0]>1 && !nr.a[nr.a[0]]) --nr.a[0];
           if (nr<y) continue;
           unsigned p,u;
           long double num1=(long double) base * nr.a[m+1] + (long double)nr.a[m];
           long double num2=(long double) y.a[m];
           if (m>1){
                    num1=num1*base + (long double) nr.a[m-1];
                    num2=num2*base + (long double)  y.a[m-1];
                    }
           if (m>2) p=(unsigned) (num1/(num2+1)); else p=(unsigned) (num1/num2);
           cat=y;
           cat*=p;
           if (m>2) u = (unsigned) ((num1+1)/(num2-1)); else u=p;
           if (u>p && cat+y<=nr) cat=cat+y, ++p;
           nr=nr-cat;
       }
       nr.semn=x.semn*y.semn;
       return nr;   
}

int operator==(const BigInt &x, const BigInt &y)
{
    for (unsigned i=0; i<=y.a[0]; i++)
        if (x.a[i]!=y.a[i]) return 0;
    return 1;
}

int operator!=(const BigInt &x, const BigInt &y)
{
    return !(x == y);
}

int operator<(const BigInt &y, const BigInt &x)
{
    if (y.a[0]<x.a[0]) return 1;
    if (y.a[0]>x.a[0]) return 0;
    unsigned k=y.a[0];
    while (x.a[k]==y.a[k] && k) k--;
    return (y.a[k]<x.a[k]);
}

int operator<=(const BigInt &y, const BigInt &x)
{
    if (y.a[0]<x.a[0]) return 1;
    if (y.a[0]>x.a[0]) return 0;
    unsigned k=y.a[0];
    while (x.a[k]==y.a[k] && k) k--;
    return (y.a[k]<=x.a[k]);
}

int operator>(const BigInt &y, const BigInt &x)
{
    return !(y <= x);
}

int operator>=(const BigInt &y, const BigInt &x)
{
    return !(y < x);
}

void BigInt::write(FILE *f) const
{
     int i,n=a[0];
     if (semn==-1) fprintf(f, "-");
     fprintf(f, "%u", a[n]);
     for (i=n-1; i>0; i--)
         fprintf(f, "%.9u", a[i]);
     fprintf(f, "\n");
}

void BigInt::read(FILE *f)
{
     char c=0;
     while (c<'0' || c>'9') c=fgetc(f); //trebuie sa fie sigur ca e un numar de citit aici
     string s="000000000"; 
     while (c>='0' && c<='9') s+=c, c=fgetc(f);
     int i, j, n=s.length()/9, lung=s.length()%9;
     a.resize(n+2);
     memset(&a[0], 0, sizeof(unsigned)*(n+2));
     if (!lung) lung=9, n--;
     for (i=1; i<=n; i++)
         for (j=lung; j<lung+9; j++)
             a[i]=a[i]*10 + (s[(n-i)*9+j]-'0');        
     a[0]=n;
     while (!a[a[0]] && a[0]>0) a[0]--;
}

int main()
{
    freopen("next.in", "r", stdin);
    freopen("next.out", "w", stdout);
    BigInt a, b, c;
    a.read(stdin);
    b.read(stdin);
    c=a%b;
    if (c!=0) c=b-c; else c=0;
    a=a+c;
    a.write(stdout);
    return 0;
}