二进制的最大公约数
对于任意给定的两个二进制数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; }