# SDOI2009[SuperGCD]

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

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-26

DESCRIPTION:

*/

#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”);

}

}