二进制的最大公约数
对于任意给定的两个二进制数B1,B2 (0< B1,B2<21000), 你的任务是在最短时间内说出它们的最大公约数。
【输入】
第一行输入一个正整数n（0≤n≤1000）,表示测试数据的次数
随后有n行测试数据，每行有两个二进制数，两个数据之间有一个或多个空格。
【输出】
输出每行给定的两个二进制数的最大公约数
【 输入样例 】
2
100 1000
100 110
【 输出样例 】
100
10
测试数据
4
100 1000
100 110
1001101000 111010100
1100100011100001 11001111111110
输出结果
100
10
100
1001011101
算法一：
#include<stdio.h>
#include<string.h>
void fun(long n)
{
if(n)
{
fun(n/2);
printf("%ld",n%2);
}
}
int main()
{
long B1,B2,t;
char szLine1[1000],szLine2[1000];
int i,n,k,nLen1,nLen2,ret;
scanf("%d",&n);
for(k=0;k<n;k++)
{
ret=0;
scanf("%s",szLine1);
scanf("%s",szLine2);
nLen1=strlen(szLine1);
nLen2=strlen(szLine2);
for(i=0;i<nLen1;i++)
{
ret*=2;
ret+=(szLine1[i]-48);
}
B1=ret;
ret=0;
for(i=0;i<nLen2;i++)
{
ret*=2;
ret+=(szLine2[i]-48);
}
B2=ret;
if(B1<B2)
{t=B1;B1=B2;B2=t;}
while(B2)
{
t=B1�;
B1=B2;
B2=t;
}
fun(B1);
printf("\n");
}
return 0;
}
算法二：
#include <stdio.h>
#include <string.h>
#define MAXN 1000
struct BigNumber{
int len;
int v[MAXN];
};
bool isSmaller(BigNumber n1,BigNumber n2)
{
if(n1.len<n2.len)
return 1;
if(n1.len>n2.len)
return 0;
for(int i=n1.len-1;i>=0;i--)
{
if(n1.v[i]<n2.v[i])
return 1;
if(n1.v[i]>n2.v[i])
return 0;
}
return 0;
}
BigNumber minus(BigNumber n1,BigNumber n2)
{
BigNumber ret;
int borrow,i,temp;
ret=n1;
for(borrow=0,i=0;i<n2.len;i++)
{
temp=ret.v[i]-borrow-n2.v[i];
if(temp>=0)
{
borrow=0;
ret.v[i]=temp;
}
else
{
borrow=1;
ret.v[i]=temp+2;
}
}
for(;i<n1.len;i++)
{
temp=ret.v[i]-borrow;
if(temp>=0)
{
borrow=0;
ret.v[i]=temp;
}
else
{
borrow=1;
ret.v[i]=temp+2;
}
}
while(ret.len>=1 && !ret.v[ret.len-1])
ret.len--;
return ret;
}
BigNumber div2(BigNumber n)
{
BigNumber ret;
ret.len=n.len-1;
for(int i=0;i<ret.len;i++)
ret.v[i]=n.v[i+1];
return ret;
}
void gcd(BigNumber n1,BigNumber n2)
{
long b=0,i;
while(n1.len && n2.len)
{
if(n1.v[0])
{
if(n2.v[0])
{
if(isSmaller(n1,n2))
n2=minus(n2,n1);
else
n1=minus(n1,n2);
}
else
n2=div2(n2);
}
else
{
if(n2.v[0])
n1=div2(n1);
else
{
n1=div2(n1);
n2=div2(n2);
b++;
}
}
}
if(n2.len)
for(i=n2.len-1;i>=0;i--)
printf("%d",n2.v[i]);
else
for(i=n1.len-1;i>=0;i--)
printf("%d",n1.v[i]);
while(b--)
printf("0");
printf("\n");
}
int main()
{
int cases,le,i;
BigNumber n1,n2;
char str1[MAXN],str2[MAXN];
scanf("%d",&cases);
while(cases--)
{
scanf("%s%s",str1,str2);
le=strlen(str1);
n1.len=le;
for(i=0;i<le;i++)
n1.v[i]=str1[le-1-i]-'0';
le=strlen(str2);
n2.len=le;
for(i=0;i<le;i++)
n2.v[i]=str2[le-1-i]-'0';
gcd(n1,n2);
}
return 0;
}