首页 > 其他 > 详细

vijos1047题解

时间：2014-02-22 05:28:14      阅读：358      评论：0      收藏：0      [点我收藏+]

总算编好了这一题，我表示200+行，亚历山大。
题目描述很简单，做起来不简单啊。（高精度的取模和除法不是一般的恶心！）
先说一下非高精度的一般做法。
求两个数a,b的最小公倍数，就是a、b的乘积与a、b的最大公因数的商。即：lcm(a,b)=a*b/gcd(a,b);
然而，如果a，b都是高精度数，我们不仅要算乘法和除法（看这个式子就知道了），还要有减法（因为mod运算中，c mod d=c-cdiv d*d)
求gcd(a,b)（最大公因数）一般有两种方法：辗转相除法（见http://baike.baidu.com/link?url=7yVbCI_TCmVcqMbEu_BgYb0ejvSJDZVmkw9g0UjrMU_3yaHAAFABgfjuk1ZT5rgI）和更相减损法（见http://baike.baidu.com/view/1340422.htm）。
 
-----------------------------------------------我是华丽的分界线--------------------------------------------------------------

一开始的时候，为了避免麻烦的除法和取模，我想用更相减损法（虽然辗转相除法快很多）。
更相减损法简介：a和b为操作数。（设a=48,b=30）
（1）把a和b的2的因数都约掉（不约也没事，但这样更快）。如：变成a=24,b=15。
（2）若a>b，a=a-b；若b>a,b=b-a;
（3）重复（2）的操作，直到a和b相等。
如： (24,15)->(9,15)->(9,6)->(3,6)->(3,3)，即最大公因数为3*2=6。
 
-----------------------------------------------我是华丽的分界线--------------------------------------------------------------
 
 我好不容易编完、调试好后，发现超时严重哪！
原来，假设有两个数a=1999,b=1。求他们的最大公因数时，按照更相减损法的步骤，会进行1999次上下！！
即：a=a-b=1999-1=1998;
       a=a-b=1998-1=1997;
      …………
那么我们可以设想，如果a=10000000000000,b=1，我的程序会怎么样？！

-----------------------------------------------我是华丽的分界线--------------------------------------------------------------

思考再三，我决定编辗转相除法。
首先我们要研究如何编高效的除法运算。二分有很好的效果。
基本思路：设a/b，a的位数是k1位，b的位数k2位。那么我们的答案ans=erfen（l,r)。其中一开始时，l=10000……（共k2-k1位），r=99999……（共k2-k1+1位）。二分的思路就是，如果当前的mid*b>a,向左二分，否则向右二分。
取模运算和除法几乎一样，只是后来要减一下，即a mod b=a-ans*b。
其他原理差不多，为了提高效率，我也先除了2。

-----------------------------------------------我是华丽的分界线--------------------------------------------------------------
代码一：更相减损法（只过了三个点）
#include<stdio.h>
#include<cstring>

using namespace std;
struct arr
{
  long num,p[101];
  arr() {num=0;memset(p,0,sizeof(p));}
}a,b,ans;
long i,tot;
char u;
bool w[10001];
void change()
{
  long i,t;
  for(i=1;i<=a.num/2;i++){t=a.p[i];a.p[i]=a.p[a.num-i+1];a.p[a.num-i+1]=t;}
  for(i=1;i<=b.num/2;i++){t=b.p[i];b.p[i]=b.p[b.num-i+1];b.p[b.num-i+1]=t;}
}
arr chen(arr a,arr b)
{
  long i,j;
  arr CHEN;
  for (i=1;i<=a.num;i++)
    for (j=1;j<=b.num;j++)
      CHEN.p[i+j-1]+=a.p[i]*b.p[j];
  CHEN.num=a.num+b.num-1;
  for (i=1;i<=CHEN.num;i++)
    if (CHEN.p[i]>9){CHEN.p[i+1]+=CHEN.p[i]/10;CHEN.p[i]%=10;}
  while (CHEN.p[CHEN.num+1]>0)
  {
    CHEN.num++;
    CHEN.p[CHEN.num+1]+=CHEN.p[CHEN.num]/10;
    CHEN.p[CHEN.num]%=10;
  }
  return CHEN;
}
arr add(arr a,arr b)
{
  long i,x=0;arr ADD;
  ADD.num=a.num;if (b.num>ADD.num)ADD.num=b.num;
  for (i=1;i<=ADD.num;i++)
    {
      ADD.p[i]=a.p[i]+b.p[i]+x;
      x=ADD.p[i]/10;ADD.p[i]%=10;
    }
   while (x>0)
   {
     ADD.num++;
     ADD.p[ADD.num]=x%10;
     x=x/10;
   }
  return ADD;
}
arr jian(arr a,arr b)
{
  long i=1,j,k;
  while (i<=b.num)
  {
    if (a.p[i]>=b.p[i])a.p[i]=a.p[i]-b.p[i];
    else
    {
      j=i+1;
      while (a.p[j]==0) j++;
      a.p[j]--;
      for (k=i+1;k<j;k++) a.p[k]=9;
      a.p[i]=a.p[i]+10-b.p[i];
    }
    i++;
  }
  while (a.p[a.num]==0) a.num--;
  return a;
}
long check(arr a,arr b)
{
  if (a.num>b.num) return 1;
  if (a.num<b.num) return -1;
  for (long i=a.num;i>0;i--)
  {
    if (a.p[i]>b.p[i]) return 1;
    else if (a.p[i]<b.p[i]) return -1;
  }
  return 0;
}
void kick()
{
  long x,i;
  while (a.p[1]%2==0&&b.p[1]%2==0)
  {
    x=0;
    for  (i=a.num;i>0;i--)
    {
      a.p[i]=(a.p[i]+x*10);
      x=a.p[i]%2;
      a.p[i]/=2;
    }
    x=0;
    for  (i=b.num;i>0;i--)
    {
      b.p[i]=(b.p[i]+x*10);
      x=b.p[i]%2;
      b.p[i]/=2;
    }
    tot++;
  }
}     
void make()
{
  long temp;long i,j,k,flag=1,x;bool boo=true;
  while (0==0)
  {
    temp=check(a,b);
    if (temp==0) break;
    k++;if (temp==1)
    {
      w[k]=true;
      a=jian(a,b);
    }
    else 
    {
      w[k]=false;
      b=jian(b,a);
    }
  }
  ans=a;
  for (i=2;i<=a.num;i++) a.p[i]=0;
  for (i=2;i<=b.num;i++) b.p[i]=0;
  a.p[1]=1;b.p[1]=1;a.num=1;b.num=1;
  for (i=k;i>0;i--)
  {
    if (w[i]) a=add(a,b);
    else b=add(a,b);
  }
  a=chen(a,b);
  ans=chen(a,ans);
  for (i=1;i<=tot;i++)
  {
    x=0;
    for (j=1;j<=ans.num;j++)
    {
      ans.p[j]=ans.p[j]*2+x;
      x=ans.p[j]/10;
      ans.p[j]%=10;
    }
    if (ans.p[ans.num+1]>0) ans.num++;
  }
}
int main()
{
  scanf("%c",&u);a.num=0;
  while (u!=‘ ‘)
  {
    a.num++;a.p[a.num]=u-48;
    scanf("%c",&u);
  }
  b.num=0;
  while (scanf("%c",&u)!=EOF)
  {
    b.num++;b.p[b.num]=u-48;
  }
  change();
  kick();
  make();
  for (i=ans.num;i>0;i--)
    printf("%ld",ans.p[i]);
  return 0;
}
代码二：辗转相除法（全过） 
#include<stdio.h>
#include<cstring>

using namespace std;
struct arr
{
  long num,p[301];
  arr() {num=1;memset(p,0,sizeof(p));}     //定义一个结构体，方便调用。ORZ 任轩笛的教导
}a,b,ans,plusone;
long i,tot;
char u;
void change()                                       //读进来是正的，处理是反的，倒一下。
{
  long i,t;
  for(i=1;i<=a.num/2;i++){t=a.p[i];a.p[i]=a.p[a.num-i+1];a.p[a.num-i+1]=t;}
  for(i=1;i<=b.num/2;i++){t=b.p[i];b.p[i]=b.p[b.num-i+1];b.p[b.num-i+1]=t;}
}
long check(arr a,arr b)                             //检验a和b的大小（高精度）
{
  if (a.num>b.num) return 1;
  if (a.num<b.num) return -1;
  for (long i=a.num;i>0;i--)
  {
    if (a.p[i]>b.p[i]) return1;
    else if (a.p[i]<b.p[i]) return-1;
  }
  return 0;
}
void kick()                                          //除掉因数2（可以没有此段）
{
  long x,i;
  while(a.p[1]%2==0&&b.p[1]%2==0)
  {
    x=0;
    for (i=a.num;i>0;i--)
    {
      a.p[i]=(a.p[i]+x*10);
      x=a.p[i]%2;
      a.p[i]/=2;
    }
    if (a.p[a.num]==0) a.num--;
    x=0;
    for (i=b.num;i>0;i--)
    {
      b.p[i]=(b.p[i]+x*10);
      x=b.p[i]%2;
      b.p[i]/=2;
    }
    if (a.p[a.num]==0) a.num--;
    tot++;                                                         //tot最多只有300+的
  }
}   
//-------------------------------------分割线--------------------------------------
arr chen(arr a,arr b)                                     //基础的高精度乘法
{
  long i,j;
  arr CHEN;
  for (i=1;i<=a.num;i++)
    for (j=1;j<=b.num;j++)
     CHEN.p[i+j-1]+=a.p[i]*b.p[j];
  CHEN.num=a.num+b.num-1;
  for (i=1;i<=CHEN.num;i++)
    if (CHEN.p[i]>9){CHEN.p[i+1]+=CHEN.p[i]/10;CHEN.p[i]%=10;}
  while (CHEN.p[CHEN.num+1]>0)
  {
    CHEN.num++;
   CHEN.p[CHEN.num+1]+=CHEN.p[CHEN.num]/10;
    CHEN.p[CHEN.num]%=10;
  }
  return CHEN;
}
arr add(arr a,arr b)                                     //基础的高精度加法
{
  long i,x=0;arr ADD;
  ADD.num=a.num;if (b.num>ADD.num)ADD.num=b.num;
  for (i=1;i<=ADD.num;i++)
    {
     ADD.p[i]=a.p[i]+b.p[i]+x;
     x=ADD.p[i]/10;ADD.p[i]%=10;
    }
   while (x>0)
   {
     ADD.num++;
     ADD.p[ADD.num]=x%10;
     x=x/10;
   }
  return ADD;
}
arr jian(arr a,arr b)                                //基础的高精度减法
{
  long i=1,j,k;
  while (i<=b.num)
  {
    if (a.p[i]>=b.p[i])a.p[i]=a.p[i]-b.p[i];
    else
    {
      j=i+1;
      while (a.p[j]==0) j++;
      a.p[j]--;
      for (k=i+1;k<j;k++)a.p[k]=9;
     a.p[i]=a.p[i]+10-b.p[i];
    }
    i++;
  }
  while (a.p[a.num]==0&&a.num>1)a.num--;
  return a;
}
//-------------------------------------分割线--------------------------------------
arr CHU(arr a,arr b)                                //高精度除法（二分）
{
  arr l,r,mid,plusone;plusone.p[1]=1;longtemp=check(a,b),i,x;
  l.num=a.num-b.num;r.num=l.num+1;
  for (i=1;i<l.num;i++)l.p[i]=0;l.p[l.num]=1;
  for (i=1;i<=r.num;i++) r.p[i]=9;
  while (true)
  {
    mid=add(l,r);
    x=0;
    for (i=mid.num;i>1;i--)
    {
     mid.p[i]=(mid.p[i]+x*10);
      x=mid.p[i]%2;
      mid.p[i]/=2;
    }
    mid.p[1]+=x*10;if (mid.p[1]%2==1)mid.p[1]=mid.p[1]/2+1;else mid.p[1]/=2;
    if (mid.p[mid.num]==0)mid.num--;
    
    temp=check(a,chen(b,mid));
    if (temp==1) l=mid;
    if (temp==-1)r=jian(mid,plusone);
    if (temp==0||check(l,r)==0)break;
  }  
  if (temp==0) return mid;else returnl;
}
arr MOD(arr a,arr b)                                      //高精度求余数
{
  arr l,r,mid,mod,plusone;plusone.p[1]=1;longtemp=check(a,b),i,x;
  l.num=a.num-b.num;r.num=l.num+1;
  if (l.num==0) l.num++;
  for (i=1;i<l.num;i++)l.p[i]=0;l.p[l.num]=1;
  for (i=1;i<=r.num;i++) r.p[i]=9;
  while (true)
  {
    mid=add(l,r);
    x=0;
    for (i=mid.num;i>1;i--)
    {
     mid.p[i]=(mid.p[i]+x*10);
      x=mid.p[i]%2;
      mid.p[i]/=2;
    }
    mid.p[1]+=x*10;if (mid.p[1]%2==1)mid.p[1]=mid.p[1]/2+1;else mid.p[1]/=2;
    if (mid.p[mid.num]==0)mid.num--;
    
    temp=check(a,chen(b,mid));
    if (temp==1) l=mid;
    if (temp==-1)r=jian(mid,plusone);
    if (temp==0||check(l,r)==0)break;
  }  
  if (temp==0) mod=jian(a,chen(b,mid));elsemod=jian(a,chen(b,l));
  return mod;
}
arr gcd(arr a,arr b)                                     //辗转相除法
{
  arr mod=MOD(a,b);
  if (mod.num==1&&mod.p[1]==0) returnb;
  return gcd(b,mod);
}
void make()                                           //主要处理场地
{
  long i,j,x;
  if (check(a,b)==1) ans=gcd(a,b);elseans=gcd(b,a);            //求最大公因数
  ans=CHU(a,ans);                                                             //本来是ans=a*b/ans，为了优化，反了一下。
  ans=chen(ans,b);
  for (i=1;i<=tot;i++)                                                           //乘上2的个数
  {
    x=0;
    for (j=1;j<=ans.num;j++)
    {
      ans.p[j]=ans.p[j]*2+x;
      x=ans.p[j]/10;
      ans.p[j]%=10;
    }
    if (x>0) 
     {
       ans.num++;
      ans.p[ans.num]=x;
     }
  }
}
//-------------------------------------分割线--------------------------------------
int main()
{
  scanf("%c",&u);a.num=0;                                //字符串读入处理操作
  while (u!=‘ ‘)
  {
    a.num++;a.p[a.num]=u-48;
    scanf("%c",&u);
  }
  b.num=0;
  while (scanf("%c",&u)!=EOF)
  {
    b.num++;b.p[b.num]=u-48;
  }
  change();
  kick();
  make();
  for (i=ans.num;i>0;i--)                                         //倒着输出
    printf("%ld",ans.p[i]);
  return 0;
}


vijos1047题解

原文：http://blog.csdn.net/jiangshibiao/article/details/19615623
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！