| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
- -我这个 怎么改,超时!#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef int hugeint;
const int Base = 10000; //应不大于10000,以防乘法时溢出。
const int Capacity = 1000;
struct xnum
{
int Len;
int Data[Capacity];
xnum() : Len(0) {}
xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); }
xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; }
xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; }
int& operator[](int Index) { return Data[Index]; }
int operator[](int Index) const { return Data[Index]; }
void print(){ //添加printf()版输出.
printf("%d",Len==0?0:Data[Len-1]);
for(int i=Len-2;i>=0;i--)
for(int j=Base/10;j>0;j/=10)
printf("%d",Data[i]/j%10);
}
};
struct num
{
int f;
xnum p, q;
};
num a[100], b[100];
xnum one = 1;
num zero;
int compare(const xnum& A, const xnum& B)
{
int I;
if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1;
for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--);
if (I < 0) return 0;
return A[I] > B[I] ? 1 : -1;
}
xnum operator+(const xnum& A, const xnum& B)
{
xnum R;
int I;
int Carry = 0;
for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++)
{
if (I < A.Len) Carry += A[I];
if (I < B.Len) Carry += B[I];
R[I] = Carry % Base;
Carry /= Base;
}
R.Len = I;
return R;
}
xnum operator-(const xnum& A, const xnum& B)
{
xnum R;
int Carry = 0;
R.Len = A.Len;
int I;
for (I = 0; I < R.Len; I++)
{
R[I] = A[I] - Carry;
if (I < B.Len) R[I] -= B[I];
if (R[I] < 0) Carry = 1, R[I] += Base;
else Carry = 0;
}
while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--;
return R;
}
xnum operator*(const xnum& A, const int B)
{
int I;
if (B == 0) return 0;
xnum R;
hugeint Carry = 0;
for (I = 0; I < A.Len || Carry > 0; I++)
{
if (I < A.Len) Carry += hugeint(A[I]) * B;
R[I] = Carry % Base;
Carry /= Base;
}
R.Len = I;
return R;
}
xnum operator*(const xnum& A, const xnum& B)
{
int I;
if (B.Len == 0) return 0;
xnum R;
for (I = 0; I < A.Len; I++)
{
hugeint Carry = 0;
for (int J = 0; J < B.Len || Carry > 0; J++)
{
if (J < B.Len) Carry += hugeint(A[I]) * B[J];
if (I + J < R.Len) Carry += R[I + J];
if (I + J >= R.Len) R[R.Len++] = Carry % Base;
else R[I + J] = Carry % Base;
Carry /= Base;
}
}
return R;
}
xnum operator/(const xnum& A, const int B)
{
xnum R;
int I;
hugeint C = 0;
for (I = A.Len - 1; I >= 0; I--)
{
C = C * Base + A[I];
R[I] = C / B;
C %= B;
}
R.Len = A.Len;
while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--;
return R;
}
xnum operator/(const xnum& A, const xnum& B)
{
int I;
xnum R, Carry = 0;
int Left, Right, Mid;
for (I = A.Len - 1; I >= 0; I--)
{
Carry = Carry * Base + A[I];
Left = 0;
Right = Base - 1;
while (Left < Right)
{
Mid = (Left + Right + 1) / 2;
if (compare(B * Mid, Carry) <= 0) Left = Mid;
else Right = Mid - 1;
}
R[I] = Left;
Carry = Carry - B * Left;
}
R.Len = A.Len;
while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--;
return R;
}
xnum operator%(const xnum& A, const xnum& B)
{
int I;
xnum R, Carry = 0;
int Left, Right, Mid;
for (I = A.Len - 1; I >= 0; I--)
{
Carry = Carry * Base + A[I];
Left = 0;
Right = Base - 1;
while (Left < Right)
{
Mid = (Left + Right + 1) / 2;
if (compare(B * Mid, Carry) <= 0) Left = Mid;
else Right = Mid - 1;
}
R[I] = Left;
Carry = Carry - B * Left;
}
R.Len = A.Len;
while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--;
return Carry;
}
istream& operator>>(istream& In, xnum& V)
{
char Ch;
for (V = 0; In >> Ch;)
{
V = V * 10 + (Ch - '0');
if (cin.peek() <= ' ' || cin.peek() == '/') break;
}
return In;
}
ostream& operator<<(ostream& Out, const xnum& V)
{
int I;
Out << (V.Len == 0 ? 0 : V[V.Len - 1]);
for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V[I] / J % 10;
return Out;
}
xnum gcd(xnum a,xnum b)
{
if(compare(b,0)==0) return a;
else return gcd(b,a%b);
}
num operator*(const num& A, const num& B)
{
num R;
R.p = A.p * B.p;
R.q = A.q * B.q;
xnum x = gcd(R.p, R.q);
R.p = R.p / x;
R.q = R.q / x;
R.f = A.f * B.f;
return R;
}
num operator-(const num& A, const num& B)
{
num R;
xnum xA = A.p * B.q;
xnum xB = A.q * B.p;
R.q = A.q * B.q;
if (A.f == 0)
{
R = B;
R.f =B.f * (-1);
return R;
}
if (A.f == 1)
{
if (B.f == -1)
{
R.p = xA + xB;
R.f = 1;
}
else
{
int f = compare(xA, xB);
if (f>=0)
R.p = xA - xB;
else
R.p = xB - xA;
R.f = f;
}
}
else
{
if (B.f == -1)
{
R.p = xA + xB;
R.f = -1;
}
else
{
int f = compare(xA, xB);
if (f > 0)
R.p = xA - xB;
else
R.p = xB - xA;
R.f = -f;
}
}
xnum x = gcd(R.p, R.q);
R.p = R.p / x;
R.q = R.q / x;
return R;
}
num operator/(const num& A, const num& B)
{
num R;
R.p = A.p * B.q;
R.q = A.q * B.p;
xnum x = gcd(R.p, R.q);
R.p = R.p / x;
R.q = R.q / x;
R.f = A.f * B.f;
return R;
}
ostream& operator<<(ostream& Out, const num& V)
{
if (V.f == -1)
Out << '-';
Out << V.p;
if (!(compare(V.q, one) == 0))
Out << '/' << V.q;
return Out;
}
void output(num A)
{
if (A.f == -1)
printf("-");
A.p.print();
if (!(compare(A.q, one) == 0))
{
printf("/");
A.q.print();
}
printf("\n");
}
int main()
{
//freopen("in.txt", "r", stdin);
zero.f = 1;zero.p = 0;zero.q = 1;
int n;
int i,k;
char ch;
cin>>n;
for (i = 0; i < n; i++)
{
if (cin.peek() == '-')
{
a[i].f = -1;
getchar();
}
else
a[i].f = 1;
cin>>a[i].p;
if (compare(a[i].p, 0)== 0) a[i].f = 0;
ch = getchar();
if (ch == '/')
cin>>a[i].q;
else
a[i].q = 1;
getchar();
}
b[0].p = a[0].q;
b[0].q = a[0].p;
b[0].f = a[0].f;
output(b[0]);
num x;
xnum xx;
for (k = 1; k < n; k++)
{
b[k].p = 0;
b[k].q = 1;
b[k].f = 0;
for (i = 1; i <= k; i++)
{
x = a[i] * b[k-i];
b[k] = b[k] - x;
}
b[k] = b[k] / a[0];
//xx = gcd(b[k].p, b[k].q);
//b[k].p = b[k].p / xx;
//b[k].q = b[k].q / xx;
output(b[k]);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator