注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

SDOI2009[SuperGCD]  

2010-07-26 13:41:25|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

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

    }

}

 

  评论这张
 
阅读(731)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018