Kodowanie Efektywnych Algorytmów - Ćwiczenia 4

// Implementacja struktury BigNum, realizujacej arytmetyke wielkich liczb

struct BigNum {
// Makro słuzace do eliminowania wiodacych zer
  #define REDUCE() while(len>1 && cyf[len-1]==0) len--;
// Podstawa, przy której wykonywane sa obliczenia oraz liczba zer w podstawie
  static const int BASE=1000000000, BD=9;
// Zmienna len reprezentuje aktualna długosc liczby (liczbe cyfr), a al
// wielkosc zaalokowanej pamieci do przechowywania cyfr liczby
  int len, al;
// Wskaznik do tablicy cyfr liczby
  LL* cyf;
// Konstruktor liczby o wartosci v i zaalokowanej pamieci dla l cyfr
  BigNum(int v=0, int l=2) {
    len=1; al=l;
    cyf = new LL[al];
    REP(x,al) cyf[x]=0;
    cyf[0]=v;
    if (v>=BASE) przen(1);
  }
// Konstruktor, przypisujacy wartosc innej liczby typu BigNum
  BigNum(const BigNum &a) {
    len=al=a.len;
    cyf = new LL[al];
    REP(x,al) cyf[x]=a.cyf[x];
  }
// Destruktor
  ~BigNum(){delete cyf;}
// Funkcja przyjmuje jako parametr zapotrzebowanie na liczbe cyfr i jesli
// zapotrzebowanie jest wieksze od aktualnego rozmiaru tablicy cyfr, to dokonuje
// realokacji
  void Res(int l) {
    if (l>al) {
      l=max(l,2*al);
      LL* n = new LL[l];
      REP(x,l) n[x] = x>=al ? 0 : cyf[x];
      delete cyf;
      cyf = n;
      al = l;
    }
  }
// Funkcja dokonuje przenoszenia do starszych cyfr nadmiaru powstałego na skutek
// wykonywania operacji. Jest to jedyne miejsce w całej strukturze, gdzie
// wykonuje sie ta operacje. Parametr okresla liczbe cyfry, do której nalezy
// wykonac przenoszenie nadmiaru
  void przen(int p) {
    int	x=0;
    for(;x<p || cyf[x]<0 || cyf[x]>=BASE;x++) {
      Res(x+2);
      if(cyf[x]<0){LL i=(-cyf[x]-1)/BASE+1; cyf[x]+=i*BASE; cyf[x+1]-=i;}else
      if(cyf[x]>=BASE){LL i=cyf[x]/BASE; cyf[x]-=i*BASE; cyf[x+1]+=i;}
    }
    len=max(len,x+1);
    REDUCE();
  }
// Od tego miejsca zaczyna sie implementacja operatorów. Przepisywanie tej
// czesci kodu nie jest wymagane - nalezy przepisywac tylko te operatory, z
// których sie korzysta. Niektóre operatory korzystaja z innych - w takich
// przypadkach, przy kazdym operatorze napisane jest, implementacji jakich
// operatorów on wymaga
// Ponizsze makro pozwala skrócic zapis nagłówków operatorów
  #define OPER1(op) bool operator op (const BigNum &a) const
  /* Operatory porownawcze */
  OPER1(==) {
    if(a.len!=len) return 0;
    REP(x,len) if(cyf[x]!=a.cyf[x]) return 0;
    return 1;
  }
  OPER1(<) {
    if(len!=a.len) return len<a.len;
    int x=len-1;
    while(x && a.cyf[x]==cyf[x]) x--;
    return cyf[x]<a.cyf[x];
  }
  OPER1(>) { return a<*this; } /* Wymaga < */
  OPER1(<=) { return !(a<*this); } /* Wymaga < */
  OPER1(>=) { return !(*this<a); } /* Wymaga < */
  OPER1(!=) { return !(*this==a); } /* Wymaga == */

// Operacje dla liczb typu int
  /* Operatory Bignum - Int */
  BigNum &operator=(int a) {
    REP(x,len) cyf[x]=0;
    len=1; cyf[0]=a;
    if (a>=BASE) przen(1);
    return *this;
  }
  void operator+=(int a){cyf[0]+=a; przen(1);}
  void operator-=(int a){cyf[0]-=a; przen(1);}
  void operator*=(int a){REP(x,len) cyf[x]*=a; przen(len);}

  int operator%(int a) {
    LL w=0;
    FORD(p,len-1,0) w=(w*BASE+cyf[p])%a;
    return w;
  }
// Operacje wyłacznie na liczbach typu BigNum
  /* Operatory Bignum - Bignum */
  #define OPER2(op) BigNum& operator op (const BigNum &a)
  OPER2(+=) {
    Res(a.len);
    REP(x,a.len) cyf[x]+=a.cyf[x];
    przen(a.len);
    return *this;
  }
  OPER2(-=) {
    REP(x,a.len) cyf[x]-=a.cyf[x];
    przen(a.len);
    return *this;
  }
  OPER2(*=) {
    BigNum c(0,len+a.len);
    REP(x,a.len) {
      REP(y,len) c.cyf[y+x]+=cyf[y]*a.cyf[x];
      c.przen(len+x);
    }
    *this=c;
    return *this;
  }


  OPER2(=) {
    Res(a.len);
    FORD(x, len-1, a.len) cyf[x]=0;
    REP(x,a.len) cyf[x]=a.cyf[x];
    len=a.len;
    return *this;
  }
// Operatory słuzace do wczytywania i wypisywania liczb
// Funkcja przypisuje liczbie BigNum wartosc liczby z przekazanego wektora,
// zapisanej przy podstawie p
  /* OPERATORY DO WCZYTYWANIA - WYPISYWANIA */
  void read(const vector<int> &v,int p) { /* Wymaga += (int), *= (int) */
    *this=0;
    FORD(x,v.size()-1,0) {
      *this *= p;
      *this += v[x];
    }
  }
// Funkcja przypisuje liczbie BigNum wartosc liczby z napisu zapisanego przy
// podstawie 10
  BigNum &operator=(string a) { /* Wymaga = (int) */
    int s=a.length();
    *this=0;
    Res(len=s/BD+1);
    REP(x,s) cyf[(s-x-1)/BD]=10*cyf[(s-x-1)/BD]+a[x]-'0';
    REDUCE();
    return *this;
  }
// Funkcja wypisuje wartosc liczby BigNum zapisanej przy podstawie 10
  void write() const {
    printf("%d", int(cyf[len-1]));
    FORD(x,len-2,0) printf("%0*d", BD, int(cyf[x]));
  }
// Funkcja wypisuje do przekazanego bufora wartosc liczby zapisanej przy
// podstawie 10
  void write(char *buf) const {
    int p = sprintf(buf, "%d", int(cyf[len-1]));
    FORD(x,len-2,0) p += sprintf(buf+p, "%0*d", BD, int(cyf[x]));
  }

  /* Inne operatory */
// Operator przesuniecia w prawo o n cyfr w prawo  
  BigNum &operator<<=(int ile) {
    if(cyf[0]==0 && len==1) return *this;
    Res(len+ile);
    FORD(x,len-1,0) cyf[x+ile]=cyf[x];
    REP(x,ile) cyf[x]=0;
    len+=ile;
    return *this;
  }
// Operator przesuniecia w prawo o n cyfr w lewo
  BigNum &operator>>=(int ile) {
    if(ile>=len) ile=len;
    REP(x,len-ile) cyf[x]=cyf[x+ile];
    FOR(x,len-ile,ile) cyf[x]=0;
    len-=ile;
    if(len==0) len=1;
    return *this;
  }

  BigNum sqrt() { /* Wymaga <, += (BigNum), *= (BigNum), <<= (int), + (BigNum), * (BigNum), << (int) */
    int n=(len+1)/2;
    BigNum a(0,n), sq;
    FORD(i,n-1,0) {
      int l=0, r=BASE-1;
      while(l<r) {
        int m=(l+r+1)/2;
        if (*this < sq+(a*2*m<<i)+(BigNum(m)*m<<2*i))
        r=m-1;
        else
        l=m;
      }
      sq+=(a*2*l<<i)+(BigNum(l)*l<<2*i);
      a.cyf[i]=l; a.len=n;
    }
    return a;
  }
// Makra pozwalajace na skrócenie zapisu nagłówków ponizszych operatorów
  #define OPER3(op) BigNum operator op(const BigNum &a) const {BigNum w=*this;  w op ## = a;  return w; }
  #define OPER4(op) BigNum operator op(int a) {BigNum w = *this; w op ## = a; return w; }
  OPER3(+); /* Wymaga += (BigNum) */
  OPER3(-); /* Wymaga -= (BigNum) */
  OPER3(*); /* Wymaga *= (BigNum) */

  OPER4(<<); /* Wymaga <<= (int) */
  OPER4(>>); /* Wymaga >>= (int) */
};

// Implementacja liczb całkowitych bazujaca na typie BigNum
int Signum(int x){return x>0?1:(x==0?0:-1);}
int Abs(int x){return x>=0?x:-x;}
struct Integer{
  BigNum x;
  int sgn; //Znak liczby: -1 dla ujemnych, 0 dla zera, 1 dla dodatnich
// Konstruktor, przyjmujacy jako parametry wartosc bezwzgledna oraz znak
// tworzonej liczby
  Integer(const BigNum &a, const int &znak) {x = a; sgn = znak;}
  Integer(const BigNum &a){x = BigNum(a); sgn = a > BigNum(0);}
// Konstruktor tworzacy zmienna równa liczbie a
  Integer(const int &a = 0){x = BigNum(Abs(a)); sgn = Signum(a);}
// Operator zwraca liczbe o przeciwnym znaku
  Integer operator- () const {return Integer(x, sgn*-1);}
// Operatory porównawcze
  bool operator<(const Integer &b) const{
    if (sgn != b.sgn) return sgn < b.sgn;
    if (sgn == -1) return b.x < x;
    return x < b.x;
  }
  bool operator==(const Integer &b) const{return sgn == b.sgn && x == b.x;}
// Makra pozwalajace na skrócenie zapisu nagłówków operatorów
  #define OPER5(op) Integer operator op (const Integer &b) const
  OPER5(-) {return *this + (-b);}
  OPER5(+) {
    if (sgn == -1) return -(-(*this) + (-b));
    if (b.sgn >= 0) return Integer(x + b.x, min(1, sgn + b.sgn));
    if (x < b.x) return Integer(b.x - x, -1);
    return Integer(x - b.x, x > b.x);
  }
  OPER5(*){ return Integer(x*b.x, sgn*b.sgn);}

  #define OPER6(op) Integer &operator op ## = (const Integer &b) {return *this = *this op b;}
  OPER6(+)
  OPER6(-)
  OPER6(*)

// Funkcja wypisuje liczbe Integer zapisana przy podstawie 10 na
// standardowe wyjscie
  void write() const{if (sgn==-1) printf("-"); x.write();}
};

BigNum NatNWD(const BigNum &a,const BigNum& b){return b==BigNum(0) ? a: NatNWD(b, a%b);}
struct Frac{
  Integer a,b;
  Frac(const Integer &aa=0,const Integer &bb=1){
    a = aa; b = bb;
    if(b<0) { a=-a; b=-b; }
    Integer d = Integer(NatNWD(aa.x,bb.x));
    a/=d; b/=d;
  }
  bool operator<(const Frac&x) const { return a*x.b < x.a*b;}
  bool operator==(const Frac&x) const { return a == x.a && b == x.b;}
  #define OPER7(op) Frac operator op (const Frac &x) const
  OPER7(+){ return Frac(a*x.b+b*x.a,b*x.b); }
  OPER7(-){ return Frac(a*x.b-b*x.a,b*x.b); }
  OPER7(*){ return Frac(a*x.a,b*x.b); }
  OPER7(/){ return Frac(a*x.b,b*x.a); }
  bool isZero(){return a==Integer(0);}
  void write(){a.write();printf("/");b.write();}
  #define OPER8(op) Frac &operator op ## =(const Frac &b) {return *this = *this op b;}
  OPER8(+)
  OPER8(-)
  OPER8(*)
  OPER8(/)
};

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define MP make_pair
#define FOR(v,p,k) for(int v=p;v<=k;++v)
#define FORD(v,p,k) for(int v=p;v>=k;--v)
#define REP(i,n) for(int i=0;i<(n);++i)
#define VAR(v,i) __typeof(i) v=(i)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i)
#define PB push_back
#define ST first
#define ND second
#define SIZE(x) (int)x.size()
#define ALL(c) c.begin(),c.end()

Zadania do wykonania