ACM高手请进

来源：百度知道 编辑：UC知道 时间：2024/09/22 11:44:18
Description

One day, Alice got a very big rectangle and wanted to divide it into small square pieces. Now comes a problem: if all pieces of small squares are of the same size, how big could the squares be? To Alice, it is easy to solve the problem. However, she is very busy, so she asked you to help her. Could you write a program to help her to solve this problem?
The length and width of the big rectangle is given, you should tell her the longest length for the small square. All of these numbers are in their binary representations.

Input

The first lien of the input is a positive integer. This is the number of the test cases followed. Each test case contains two integer L and W in their binary representation which tells you the length and width of the very big rectangle( 0 < L, W < 2^1000). There may be one or several spaces between these integers.

Output

The output of the problem should consistsof one line of output

你需要的是高精度的gcd算法～
两个高精度数，
如果都是偶数，比如2a,2b，那么(2a,2b)=2(a,b)
如果有一个奇数，比如2a,2b+1，那么（2a,2b+1）=(a,2b+1)
如果都是奇数，比如2a+1，2b+1，那么（2a+1，2b+1）＝（两个数加起来，两个数减一下）

#include <stdio.h>
#include <string.h>
#include <math.h>

//将二进制数转换成十进制数
int btod(char str[], int size);

//辗转相除法求最大公约数，即找到题中适合的正方形边长
int gcd(int m, int n);

//将十进制数转换为二进制数并输出结果
void dtob(int n);

int main()
{
int cases = 0; //设置要处理的次数
int size, length, width, side;//分别记录当前二进数有几位，矩形的长、宽，所求得的正方形的边长

scanf("%d", &cases);
for(int k=0; k<cases; ++k)
{
char l_array[20], w_array[20];

scanf("%s %s", l_array, w_array);
size = strlen(l_array);
length = btod(l_array, size);
size = strlen(w_array);
width = btod(w_array, size);

side = gcd(length, width);
dtob(side);
}
}

//将二进制数转换