#include <iostream>
#include <string>
using namespace std;

typedef  long long _BigInt;
const int BITSIZE = 7000;
const int EACHBITNUM = 100000000;
class BIGINT
{
public:
	_BigInt size;
	_BigInt data[BITSIZE];
	BIGINT();
	BIGINT(string);
	BIGINT operator=(const BIGINT&);
	bool operator<(const BIGINT &);
	bool operator==(const BIGINT &);
	bool operator>(const BIGINT &);
	bool operator<=(const BIGINT &);
	bool operator>=(const BIGINT &);
	bool operator!=(const BIGINT &);
	friend BIGINT operator+(const BIGINT&, const BIGINT&);
	friend BIGINT operator-(BIGINT, BIGINT);
	friend BIGINT operator*(const BIGINT &, const BIGINT &);
	void print();
};

BIGINT::BIGINT()
{
	size = 0;
	memset(data, 0, sizeof(data));
}

BIGINT::BIGINT(string s)
{
	int i;
	int len = s.length();
	int exp = 1;
	_BigInt tmp = 0;
	size = 0;
	memset(data, 0, sizeof(data));
	for (i=len; i>=1; i--)
	{
		tmp += (s[i-1] - '0') * exp;
		if (exp == EACHBITNUM/10)
		{	
			data[++size] = tmp;
			tmp = 0;
			exp = 1;
		}
		else
			exp *= 10;
	}
	if (tmp != 0)
		data[++size] = tmp;
}

BIGINT BIGINT::operator=(const BIGINT &a)
{
	int i;
	memset(data, 0, sizeof(data));
	size = a.size;
	for (i=1; i<=size; i++)
		data[i] = a.data[i];
	return *this;
}
void BIGINT::print()
{
	int i;
	for (i=size; i>=1; i--)
	    if (i != size)
		   printf("%.8lld", data[i]);
        else
           printf("%lld", data[i]);
	printf("\n");
}
bool BIGINT::operator<(const BIGINT &a)
{
     int i;
     if (size < a.size) return true;
     if (size > a.size) return false;
     for (i=1; i<=size; i++)
         if (data[i] >= a.data[i]) return false;
     return true;     
}
bool BIGINT::operator==(const BIGINT &a)
{
     int i;
     if (size != a.size) return false;
     for (i=1; i<=size; i++)
         if (data[i] != a.data[i]) return false;
     return true;
}
bool BIGINT::operator>(const BIGINT &a)
{
     int i;
     if (size > a.size) return true;
     if (size < a.size) return false;
     for (i=1; i<=size; i++)
         if (data[i] <= a.data[i]) return false;
     return true;  
}
bool BIGINT::operator>=(const BIGINT &a)
{
     return !((*this) < a);
}
bool BIGINT::operator<=(const BIGINT &a)
{
     return !((*this) > a);
}
bool BIGINT::operator!=(const BIGINT &a)
{
     return !((*this) == a);
}
BIGINT operator+(const BIGINT &a, const BIGINT &b)
{
	BIGINT rnt;
	int i;
	bool t = false;
	_BigInt tmp;
	int len = a.size > b.size ? a.size : b.size;
	for (i=1; i<=len; i++)
	{
		tmp = a.data[i] + b.data[i];
		if (t) tmp += 1;
		t = false;
		if (tmp >= EACHBITNUM)
		{
			tmp -= EACHBITNUM;
			t = true;
		}
		rnt.data[++rnt.size] = tmp;
	}
	if (t) rnt.data[++rnt.size] += 1; 
	return rnt;
}
BIGINT operator-(BIGINT a, BIGINT b)
{
       BIGINT rnt;
       int i;
      // if (a < b) return rnt;
       for (i=1; i<=a.size; i++)
       {
           if (a.data[i] < b.data[i])
           {
               a.data[i+1]--;
               a.data[i] += EACHBITNUM;
           }
           rnt.data[++rnt.size] = a.data[i] - b.data[i];
       }
       return rnt;
}
BIGINT operator*(const BIGINT &a, const BIGINT &b)
{
       int i, j;
       BIGINT rnt;
       _BigInt tmp;
       for (i=1; i<=a.size; i++)
           for (j=1; j<=b.size; j++)
           {
               tmp = a.data[i] * b.data[j];
               rnt.data[i+j-1] += tmp;
               rnt.data[i+j] +=  rnt.data[i+j-1] / EACHBITNUM;
               rnt.data[i+j-1] %= EACHBITNUM;
           }
       for (i=BITSIZE-1; i>=1; i--)
           if (rnt.data[i] > 0 || i == 1)
           {
               rnt.size = i;
               break;
           }
       return rnt;
}
int main()
{    
    int n;
    int i;
   // BIGINT tmp;
    BIGINT one("1");
    BIGINT y("1");
    cin >> n;

   for (i=1; i<=n; i++)
   {
      y = y + one;
      y.print();
      y = y * (y - one);
   }
   //system("pause");
	return 0;
}

• Re:请问怎么优化高精度, TLE得不行了 (14) HYSBZ 2006-08-24 00:15:39
  • 我已经逢100000000进一了， 不过改成1000000000ac, 但是要900毫秒-_- (20) howie 2006-08-24 02:38:39
    • 现在逢100000000进一了可以ＡＣ了，但是要900多ＭＳ， 不过改成1000000000ac, 还要７００多ＭＳ (0) dongshanluo 2007-08-28 15:02:39