首页 > 代码库 > X_unsigned

X_unsigned

//X10.h
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <windows.h>

typedef unsigned long long ull;

using namespace std;

const int pinitsz = 10000;
const ull F_32 = 0x00000000FFFFFFFF, F_64 = 0xFFFFFFFFFFFFFFFF, allbits = F_64;
ull *makee10s() {
  ull *x = new ull[20];
  x[0] = 1;
  for (int i = 1; i < 20; ++i)
    x[i] = x[i - 1] * 10;
  return x;
}
const ull *E10s = makee10s();
#include "X10.h"

class xu {
public:
  ull * d;
  int lt, sz, initsz;
    xu() {
    sz = initsz = pinitsz;
    lt = -1;
    d = new ull[sz];
  } ~xu() {
    delete[]d;
  }
  xu(const xu & x) {
    sz = x.sz;
    lt = x.lt;
    d = new ull[sz];
    memcpy(d,x.d,(lt+1)<<3);
  }
  xu(const char *s) {
    lt = (d[0] = 0);
    for (int i = 0; s[i] != 0; ++i) {
      (*this) *= 10;
      d[0] += s[i] - 48;
    };
  }
  xu & operator =(const xu & x) {
      if(d!=x.d){
    sz = x.sz;
    lt = x.lt;
    delete[]d;
    d = new ull[sz];
    memcpy(d,x.d,(lt+1)<<3);
      }
    return *this;
  }
  xu & operator =(const ull & x) {
    lt = (x == 0 ? -1 : 0);
    d[0] = x;
    return *this;
  }
  xu & operator =(const char *s) {
    lt = -1;
    d[0] = 0;
    unsigned k;
    int i, j;
    for (i = 0; s[i] != 0; i += 9) {
      k = 0;
      for (j = i; j < i + 9; ++j) {
        if (s[j] < 0 || s[j] > 9) {
          (*this) *= E10s[j - i];
          (*this) += (xu) k;
          return *this;
        }
        k = k * 10 + s[j] - 48;
      }
      (*this) *= 1000000000;
      (*this) += (xu) k;
    }
    return *this;
  }
  xu(const ull & x) {
    sz = 1;
    d = new ull[sz];
    lt=(d[0] = x)!=0?0:-1;
  }
  xu(const ull & x, int s) {
    sz = s;
    d = new ull[sz];
    lt=(d[0] = x)!=0?0:-1;
  }
  void enlarge(int s) {
    if (s < initsz)
      s = initsz;
    sz += s;
    initsz=sz;
    ull *nd = new ull[sz];
    memcpy(nd,d,(lt+1)<<3);
    delete[]d;
    d = nd;
  }

  void indec() {
    lt = (d[0] = 0);
    char s[65536] = { };
    scanf("%s", s);
    for (int i = 0; s[i] != 0; ++i) {
      (*this) *= 10;
      d[0] += s[i] - 48;
    }
  }
  void outdec() {
    if (lt <= 0) {
      printf("%llu\n", d[0]);
      return;
    }
    int osz = lt * 7 / 3 + 3, i, olt = -1;
    ull *n = new ull[osz], up;
    for (i = 0; i < osz; n[i++]=0);
    const unsigned E9 = 1000000000;
    for (int j = lt; j >= 0; --j) {
      for (i = 0; i <= olt; n[i++]<<=32);
      n[0] |= (d[j] >> 32);
      for (i = up = 0; i < olt + 3; ++i) {
        up = (n[i] += up) / E9;
        n[i] -= up * E9;
      }
      olt+=((n[olt + 2] != 0)?2:1);
      for (i = 0; i <= olt; n[i++]<<=32);
      n[0] |= (d[j] & F_32);
      for (i =up= 0; i < olt + 3; ++i) {
        up = (n[i] += up) / E9;
        n[i] -= up * E9;
      }
      olt+=((n[olt + 2] != 0)?2:1);
    }
    while (n[olt--] == 0);
    printf("%llu", n[olt+1]);
    for (i = olt ; i >= 0; --i) {
      printf("%09llu", n[i]);
    }
    printf("\n");
  }
  void outhex() {
    for (int i = lt; i >= 0; --i) {
      printf("%08X", (unsigned)(d[i] >> 32));
      printf("%08X", (unsigned)d[i]);
    }
    printf("\n");
  }

  xu & l_move64(int step) {
    if (lt + step + 2 > sz) {
      enlarge(step);
    }
    int i=(lt+=step);
    for (; i >=step;d[i]=d[(i--)-step]);
    while (i >= 0)
      d[i--] = 0;
    return *this;
  }
  xu & operator <<=(unsigned step) {
    if (step >= 64) {
      l_move64(step >> 6);
      step &= 63;
    }
    if(step==0) return *this;
    unsigned _st_ = 64 - step;
    for (int i = lt+1; i>0; d[--i]<<=step)
      d[i] |= (d[i-1] >> _st_);
    if (d[lt + 1] != 0)
      ++lt;
    return *this;
  }
  xu & r_move64(unsigned step) {
    lt -= step;
    for (int i = 0; i <= lt; ++i)
      d[i] = d[i + step];
    return *this;
  }
  xu & operator >>=(unsigned step) {
    if (step >= 64) {
      r_move64(step >> 6);
      step &= 63;
    }
    unsigned _st_ = 64 - step;
    for (int i = 0; i < lt; ++i) {
      (d[i] >>= step) |= (d[i + 1] << _st_);
    }
    if ((d[lt] >>= step) == 0)
      lt--;
    return *this;
  }

  xu & operator +=(const xu & x) {
    if (x.lt > sz - 2 || lt > sz - 2)
      enlarge(0);
    int i=lt+1;
    for (d[i]=0; i < x.lt + 2; d[i++]=0);
    for (i = 0; i <= x.lt;) {
      if ((d[i] += x.d[i]) < x.d[i]) {
        while ((d[++i] += 1) == 0)
          d[i] = x.d[i];
      } else
        ++i;
    }
    if (i > lt) {
      for (lt = i; d[lt] == 0 && lt >= 0; --lt);
    }
    return *this;
  }
  xu operator +(const xu & x) {
    xu a = (*this);
    a += x;
    return a;
  }
  xu & operator -=(const xu & x) {
    for (int i = 0; i <= x.lt;) {
      if (d[i] < (d[i] -= x.d[i])) {
        while ((d[++i] -= 1) == F_64)
          d[i] -= x.d[i];
      } else
        ++i;
    }
    while (d[lt] == 0 && lt >= 0)
      lt--;
    return *this;
  }
  xu operator -(const xu & x) {
      if(x.d==d) return (xu)((ull)0);
    xu a = (*this);
    a -= x;
    return a;
  }
  xu & operator *=(ull x) {
    if (lt > sz - 2)
      enlarge(0);
    ull a , b , c = (d[lt + 1] = 0);
    if (x == 0) {
      lt = -1;
      return *this;
    }
    if(((x-1)&x)==0){
        int i=0;
        for(;(x>>=1)!=0;++i);
        return (*this)<<=i;
    }
    if (x > F_32) {
      unsigned x1 = (unsigned)(x >> 32), x2 = (unsigned)(x & F_32);
      ull n, m = 0;
      for (int i = 0; i < lt + 2; ++i) {
        a = (d[i] >> 32) * x2;
        b = (d[i] >> 32) * x1;
        n = (d[i] & F_32) * x2;
        c = (d[i] & F_32) * x1;
        if ((d[i] = n + m) < n)
          b += 1;
        if (d[i] > (d[i] += (a << 32)))
          b += 1;
        if (d[i] > (d[i] += (c << 32)))
          b += 1;
        m = b + (a >> 32) + (c >> 32);
      }
      if (d[lt + 1])
        ++lt;
      return *this;
    }
    for (int i = 0; i <=lt; ++i) {
        a=(d[i]>>32)*x;
        if((a<<32)>(d[i]=d[i]*x+c)) c=(a>>32)+1;
        else c=(a>>32);
        /*
      a = (d[i] >> 32) * x;
      d[i] = (d[i] & F_32) * x;
      b = c;
      c = (a >> 32);
      a = ((a << 32) | b);
      if ((d[i] += a) < a)
        ++c;*/
    }
    if ((d[lt + 1]=c)!=0)
      ++lt;
    return *this;
  }
  xu operator *(ull x) {
    xu a = (*this);
    a *= x;
    return a;
  }
  xu & operator *(const xu & x) {
    xu r(lt + x.lt + 2);
    int i;

    for (i = 0; i < r.sz; ++i)
      r.d[i] = 0;
    for (i = 0; i < r.sz; ++i) {
      for (int j = 0; j <= lt; ++j) {
        ;
      }
    }
  }
  unsigned operator %(unsigned x) {
    ull r = 0;
    for (int i = lt; i >= 0; --i)
      r = ((((r << 32) + (d[i] >> 32)) % x << 32) + (d[i] & F_32)) % x;
    return r;
  }
  xu& operator /=(unsigned x) {
    ull a, b, c = 0;
    for (int i = lt; i >= 0; --i) {
      c |= (d[i] >> 32);
      b = c / x;
     a = ((c - x*b) << 32) | (d[i] & F_32);
      d[i] = a / x;
      c = ((a - x*d[i]) << 32);
      d[i] |= (b << 32);
    }
    if (d[lt] == 0)
      lt--;
    return *this;
  }
  xu & divi2(unsigned x,xu &r) {
    ull a, b, c = 0;
    for (int i = lt; i >= 0; --i) {
      c |= (d[i] >> 32);
      b = c / x;
      a = ((c -b*x) << 32) | (d[i] & F_32);
      r.d[i] = a / x;
      c = ((a -r.d[i]*x) << 32);
      r.d[i] |= (b << 32);
    }
    if (r.d[r.lt=lt] == 0)
      r.lt--;
    return *this;
  }
  xu& divi(unsigned dv) {
      if(dv==1) return *this;
    ull x = F_64 / dv, a, b, c = 0;
    if((x+1)*dv==0) x++;
    unsigned x1 = (x >> 32), x2 = (x & F_32), x3 =((-(x* dv)) << 32) / dv;
    for (int i = lt; i >= 0; i--) {
      a = (d[i] >> 32);
      c =d[i]-(d[i]=c*x+ a * x1 + ((a * x2 + (d[i]&F_32)* x1 + c * x3) >> 32))* dv;
      for (;c >= dv;c-=dv,++d[i]);
    }
    if (d[lt] == 0)
      lt--;
    return *this;
  }
  xu & divi(unsigned dv, xu & r) {
      if(r.d==d) return (*this)/=dv;
      if(dv==1) return (r=(*this));
    ull x = F_64 / dv, a, b, c = 0;
    if (r.sz < lt + 1)
      r.enlarge(lt + 1 - r.lt);
    if((x+1)*dv==0) x++;
    unsigned x1 = (x >> 32), x2 = (x & F_32), x3 =((-(x* dv)) << 32) / dv;
    for (int i = lt; i >= 0; i--) {
      a = (d[i] >> 32);
      r.d[i] = c * x + a * x1 + ((a * x2 + (d[i]&F_32) * x1 + c * x3) >> 32);
    for(c=d[i]-r.d[i]*dv;c>=dv;c-=dv,++r.d[i]);
    }
    if (r.d[r.lt = lt] == 0)
      r.lt--;
    return r;
  }
  xu operator /(unsigned x) {
    xu a = (*this);
    a /= x;
    return a;
  }
};

xu xfact(unsigned n) {
  xu r = 1;
  unsigned i = 1;
  if (n % 2) {
    r = n;
    --n;
  }
  while (n > i) {
    r *= (n * i);
    --n;
    ++i;
  }
  return r;
}

xu xpow(ull a, unsigned b) {
  xu x(1, pinitsz);
  while (b--)
    x *= a;
  return x;
}
xu calcpi(unsigned n) {
  xu a = xpow(3125*3125, n);
  a<<=(n*10);
  xu  b = a, p(0, a.lt + 2), p2(0, a.lt + 2), d=(a/=3);
  unsigned z = 1;
  b /= 7;
  while (d.lt >= 0) {
    p += d;
    b.divi(z,d);
    p2 += d;
    a /= 9;
   a.divi(z += 2,d);
    p -= d;
    b /= 49;
    b.divi(z,d);
    p2 -= d;
    a/=9;
    b/=49;
    a.divi(z+=2,d);
  }
  p <<= 1;
  p += p2;
  p <<= 2;
  return p;
}

int xtime(){
    static int t;
    int lt=t;
    t=GetTickCount();
    //struct timeval tmv;
    //gettimeofday(&tmv, NULL);
    //t = 1000*(tmv.tv_sec&0x001fffff) + tmv.tv_usec/1000;
    return t-lt;
}

int main() {
  xu x, y;
  unsigned a, t;
  char s[65536] = { };
  while(1){
      scanf("%u",&a);
      x=calcpi(a);
      x.outdec();
  }
  
  //freopen("data.txt","w",stdout);
 
  while (1) {
    scanf("%u", &a);
    //xtime();
    x = xfact(a);
   //printf("t1 %u\n", xtime());
    x.outdec();
    fflush(stdout);
    return 0;
    //printf("t2:%u\n",xtime());
  }
  x=xpow(E10s[9],12000);
 while (1) {
    scanf("%u", &a);
    y=x;
    xtime();
    for(int i=1000;i--;) y/=a;
    printf("t1 %u\n", xtime());
    y=x;
    xtime();
    for(int i=1000;i--;) y.divi(a);
    printf("t2:%u\n",xtime());
  }
  return 0;
}

 

X_unsigned