tdio.h>Рint main()Р{Р int i,j,m,n,k;Р int a[17];Р while(scanf("%d",&n)!=EOF)Р {if(n==0)Р printf("0\n");Р elseР {Р for(m=0;m<=16;m++)Р {Р i=n%2;Р j=n/2;Р n=j;Р a[m]=i;Р }Р for(m=16;m>=0;m--)Р {Р if(a[m]==1)Р {k=m;Р break;}Р }Р for(m=k;m>=0;m--)Р printf("%d",a[m]);Р printf("\n");Р }Р}Р}Р/////Problem F: 辗转相除法最大公约数的算法РDescriptionР辗转相除法,也称欧几里得算法,是求最大公约数的算法。InputР输入为多行,每行有一对非负整数a,b,且a*b不会超出int类型的数据范围。输入至EOF结束。РOutputР每行输出一对a,b的最大公约数和最小公倍数,顺序与输入对应。Р从数论上的整除定义出发:若a整除b(b除以a没有余数),则b是a的倍数,a是b的约数,这里要求b不为0。因此0是任意整数的倍数,但是0不能是约数。Р#include <stdio.h>Рint main()Р{ int a,b,c,m,t;Р while(scanf("%d %d",&a,&b)!=EOF)Р { if(a==0&&b!=0)Р printf("%d %d\n",b,a);Р else if(a!=0&&b==0)Р printf("%d %d\n",a,b);Р elseР { if(a<b){ t=a; a=b; b=t; }Р m=a*b;c=a%b;Р while(c!=0) { a=b; b=c; c=a%b; }Р printf("%d %d\n",b,m/b); }}}
全文预览
