luogu2152 [SDOI2009]SuperGCD

　　要你求两个非常大的数字的GCD。

　　不要想复杂，用高精度整更相减损术即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct BigInt
{
    static const int BASE = 10000, CARRY = 4, MAX_N = 10000;
    int A[MAX_N], Len;

    void Clear()
    {
        memset(A, 0, sizeof(A));
        Len = 0;
    }

    void Read(char *s)
    {
        int len = strlen(s);
        Clear();
        int cur = 0, pos = 0, pow = 1;
        for (int i = len - 1; i >= 0; i--)
        {
            cur += (s[i] - '0') * pow;
            pow *= 10;
            if (++pos == CARRY)
            {
                A[Len++] = cur;
                cur = pos = 0;
                pow = 1;
            }
        }
        if (!pos)
            Len--;
        else
            A[Len] = cur;
    }

    void Print()
    {
        printf("%d", A[Len]);
        for (int i = Len - 1; i >= 0; i--)
            printf("%0*d", CARRY, A[i]);
        printf("
");
    }

    void operator -= (const BigInt& a)
    {
        for (int i = 0; i <= Len; i++)
        {
            A[i] -= a.A[i];
            if (A[i] < 0)
            {
                A[i + 1]--;
                A[i] += BASE;
            }
        }
        while (A[Len] == 0 && Len > 0)
            Len--;
    }

    bool operator < (const BigInt& a) const
    {
        if (Len != a.Len)
            return Len < a.Len;
        for (int i = Len; i >= 0; i--)
            if (A[i] != a.A[i])
                return A[i] < a.A[i];
        return false;
    }

    bool operator != (const BigInt& a) const
    {
        if (Len != a.Len)
            return true;
        for (int i = Len; i >= 0; i--)
            if (A[i] != a.A[i])
                return true;
        return false;
    }
};

int main()
{
    BigInt *a = new BigInt, *b = new BigInt;
    static char s[BigInt::BASE * BigInt::CARRY];
    scanf("%s", s);
    a->Read(s);
    scanf("%s", s);
    b->Read(s);
    while (*a != *b)
    {
        if (*a < *b)
            swap(a, b);
        *a -= *b;
    }
    a->Print();
    return 0;
}