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