Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 这个大整数类，没用FFT，除了每位存4个十进制位外没啥特殊优化吧？

Posted by renew at 2009-08-25 10:21:41 on Problem 3742
In Reply To:Re:我的两个大整数类都挂了。。。 一个TLE 一个MLE 而Jave一次就过了。。。 Posted by:zjut066 at 2009-08-23 19:09:34
```#define M 10000

struct BigInt {
int a[100], len, sign;
void compact()
{
while (len > 1 && !a[len-1]) --len;
if (!len) len = 1;
if (1 == len && !a[0]) sign = 0;
}
void operator = (int n)
{
if (n < 0) sign = 1, n = -n; else sign = 0;
for (len = 0; n; ++len) a[len] = n % M, n /= M;
if (!len) a[0] = 0, len = 1;
}
void operator = (const BigInt &bi)
{
len = bi.len;
sign = bi.sign;
memcpy(a, bi.a, len * sizeof(a[0]));
}
BigInt operator * (const BigInt &bi) const
{
int i, j, k;
BigInt rs;
rs.sign = (sign ^ bi.sign);
rs.len = len + bi.len;
memset(rs.a, 0, rs.len*sizeof(a[0]));
for (i = 0; i < len; ++i)
for (j = k = 0; j < bi.len || k; ++j)
{
k += rs.a[i+j];
if (j < bi.len) k += a[i]*bi.a[j];
rs.a[i+j] = k % M;
k /= M;
}
rs.compact();
return rs;
}
bool AbsLess(const BigInt &bi) const
{
if (len != bi.len) return len < bi.len;
for (int i = len; --i >= 0; )
if (a[i] != bi.a[i]) return a[i] < bi.a[i];
return false;
}
void operator += (const BigInt &bi)
{
int i, j;
if (sign == bi.sign) {
for (i = j = 0; i < len || i < bi.len || j; ++i)
{
if (i < len) j += a[i];
if (i < bi.len) j += bi.a[i];
a[i] = j % M;
j /= M;
}
if (i > len) len = i;
} else {
if (AbsLess(bi)) {
BigInt t = *this;
*this = bi;
for (i = j = 0; i < t.len || j; ++i)
{
if (i < t.len) j += t.a[i];
a[i] -= j;
if (a[i] < 0) j = 1, a[i] += M; else j = 0;
}
} else {
for (i = j = 0; i < bi.len || j; ++i)
{
if (i < bi.len) j += bi.a[i];
a[i] -= j;
if (a[i] < 0) j = 1, a[i] += M; else j = 0;
}
}
}
compact();
}
void output()
{
int i = len;
compact();
if (sign) putchar('-');
printf("%d", a[--i]);
while (--i >= 0) printf("%04d", a[i]);
}
}```

Followed by: