SDOI2009[SuperGCD]

就是求最大公约数,需要用高精度。

然后假设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”);

    }

}