就是求最大公约数，需要用高精度。
然后假设a>=b
gcd(2*a,2*b)=2gcd(a,b)
gcd(2*a+1,2*b+1)=gcd(2*(a-b),2*b+1)
gcd(2*a,b*2+1)=gcd(a,2*b+1)
gcd(2*a+1,b*2)=gcd(2*a+1,b)
gcd(a,0)=a
还有，如果你要交到衡阳八中OJ，为了防止爆栈，请直接写非递归的，否则会像我一样，调试N久。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-7-26
DESCRIPTION:
山东2009年省选 SuperGCD
*/
#include <stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
const int MAXLENGTH=10000+2;
const int BASE=1000000000;
const int LOG10_BASE=9;
typedef int number[MAXLENGTH/LOG10_BASE+1];
typedef char string[MAXLENGTH];
string A,B;
int AL,BL;
number NA,NB;
int NAL,NBL;
void get_string(string S,int& SL)
{
char get;
SL=0;
while ((get=getchar())!=’\n’) S[SL++]=get;
S[SL]=0;
}
void get_number(number N,int& NL,string S,int SL)
{
NL=(SL+LOG10_BASE-1)/LOG10_BASE;
for (int i=SL-1,j=0;i>=0;i-=LOG10_BASE,j++)
for (int k=max(i-LOG10_BASE+1,0);k<=i;k++)
N[j]=N[j]*10+(S[k]-‘0’);
}
void print_number(number N,int NL)
{
if (!NL) printf(“0”);
else
{
printf(“%d”,N[NL-1]);
for (int i=NL-2;i>=0;i–)
printf(“%09d”,N[i]);
}
}
bool less(number A,int AL,number B,int BL)
{
if (AL==BL)
{
for (int i=AL-1;i>=0;i–)
if (A[i]!=B[i]) return A[i]<B[i];
return false;
}
else return AL<BL;
}
void dec(number A,int& AL,number B,int& BL)
{
for (int i=BL-1;i>=0;i–)
A[i]-=B[i];
for (int i=0;i<AL;i++)
if (A[i]<0) A[i+1]–,A[i]+=BASE;
while (AL>0&&A[AL-1]==0) AL–;
}
void div2(number A,int& AL)
{
for (int i=AL-1;i>=0;i–)
{
if (A[i]%2==1) A[i-1]+=BASE;
A[i]/=2;
}
while (AL>0&&A[AL-1]==0) AL–;
}
void mul2(number A,int& AL)
{
for (int i=0;i<AL;i++)
A[i]*=2;
for (int i=0;i<AL;i++)
if (A[i]>=BASE)
{
A[i]-=BASE;
if (i+1==AL) A[AL++]=1;
else A[i+1]+=1;
}
}
int main()
{
get_string(A,AL);
get_string(B,BL);
get_number(NA,NAL,A,AL),get_number(NB,NBL,B,BL);
{
number* A=&NA;
number* B=&NB;
int AL=NAL,BL=NBL;
int mul2_times=0;
for (;;)
{
if (less(*A,AL,*B,BL))
{
number* S;
S=A,A=B,B=S;
int SL;
SL=AL,AL=BL,BL=SL;
}
if (BL==0) break;
if (((*A)[0]%2==1)&&((*B)[0]%2==1)) dec(*A,AL,*B,BL);
else if (((*A)[0]%2==1)&&((*B)[0]%2==0)) div2(*B,BL);
else if (((*A)[0]%2==0)&&((*B)[0]%2==1)) div2(*A,AL);
else div2(*A,AL),div2(*B,BL),mul2_times++;
}
for (int i=0;i<mul2_times;i++)
mul2(*A,AL);
print_number(*A,AL),printf(“\n”);
}
}