输入二个二进制整数(长度不超过20位),求出其最大公约数与最小公倍数,并用二进制数

表示。

输入格式：
输入两个二进制整数，每个整数占一行，长度不超过20位，不含前导零。

输出格式：
输出一行，包含两个二进制整数的最大公约数和最小公倍数，用空格隔开。

输入样例：
10101010101010101010
11111111111111111111
输出样例：
101010101010101010 11111111111111111110101010101010101010

相关问题

输入二个二进制整数(长度不超过20位),求出其最大公约数与最小公倍数,并用二进制数输出代码c++

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

// 求两个二进制整数的最大公约数
char* binaryGcd(char* a, char* b) {
int len1 = strlen(a), len2 = strlen(b);
if (len1 < len2) {
char* tmp = a;
a = b;
b = tmp;
len1 ^= len2 ^= len1 ^= len2;
}
while (len2 > 0) {
int i = len1 - 1, j = len2 - 1;
while (i >= 0 && j >= 0 && a[i] == '0') {
i--;
}
while (i >= 0 && j >= 0 && b[j] == '0') {
j--;
}
if (i >= 0 && j >= 0) {
if (i > j) {
i = j;
}
for (int k = i; k >= 0; k--) {
if (a[k] == '1' && b[k] == '1') {
for (int l = k; l >= 0; l--) {
if (a[l] == '0') {
a[l] = '1';
} else {
a[l] = '0';
break;
}
}
for (int l = k; l >= 0; l--) {
if (b[l] == '0') {
b[l] = '1';
} else {
b[l] = '0';
break;
}
}
break;
}
}
} else {
break;
}
}
while (strlen(a) > 1 && a[0] == '0') {
for (int i = 0; i < strlen(a) - 1; i++) {
a[i] = a[i + 1];
}
a[strlen(a) - 1] = '\0';
}
return a;
}

// 求两个二进制整数的最小公倍数
char* binaryLcm(char* a, char* b) {
char* gcd = binaryGcd(a, b);
int len1 = strlen(a), len2 = strlen(b), lenGcd = strlen(gcd);
int lcmLen = len1 + len2 - lenGcd;
char* lcm = (char*)malloc(sizeof(char) * (lcmLen + 1));
lcm[lcmLen] = '\0';
for (int i = 0; i < lcmLen; i++) {
lcm[i] = '0';
}
int i = len1 - 1, j = len2 - 1, k = lcmLen - 1;
while (k >= 0) {
if (i < 0) {
lcm[k] = b[j];
j--;
} else if (j < 0) {
lcm[k] = a[i];
i--;
} else if (a[i] == '1' && b[j] == '1') {
lcm[k] = '1';
i--;
j--;
} else if (a[i] == '0' && b[j] == '0') {
lcm[k] = '0';
i--;
j--;
} else {
lcm[k] = '0';
k--;
i--;
j--;
}
}
free(gcd);
return lcm;
}

int main() {
char a[21], b[21];
scanf("%s %s", a, b);
printf("最大公约数：%s\n", binaryGcd(a, b));
printf("最小公倍数：%s\n", binaryLcm(a, b));
return 0;
}