要你求两个非常大的数字的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("\n");
} 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;
}