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

- -我这个 怎么改,超时!

Posted by nic_zy at 2008-07-12 22:53:33 on Problem 3610
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator