11412: 【原1412】GCD++
题目
题目描述
author: Mars、Taring 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1412
Description
有些事情是令人绝望的，比如Taring在NOI招生的时候想起当年他把最大公约数(GCD)函数写错了。所以他想在最后一次考试的时候考一次GCD。
Mars表示这有什么好考的，于是他扩大了数据范围且将输出格式转换成了二进制。
Input Format
第一行一个数M
第二行一个数N
Output Format
一个数，两者的最大公约数的二进制，即Gcd(M,N)。
Sample Input
7
4
Sample Output
1
数据范围
所有数据满足\( n \leq 10^{500} \)。
Hint
小数据已被Mars删除。不允许使用Java或者Python完成这道题目。
q4x3's solution
/**
* 高精度GCD + 二进制转换
* 字符串存数据
* 高精度减法没什么好说的
* 高精度取模就是补零做减法
* 辗转相除求GCD
* 再转二进制，不停地除以二就行
**/
#include <iostream>
#include <cstring>
using namespace std;
class bint {
public:
char data[600];
int len;
friend istream& operator>>(istream &in, const bint &obj);
friend ostream& operator<<(ostream &os, const bint &obj);
bint() {
len = 0;
for(int i = 0;i < 600;++ i)
data[i] = 0;
}
bint(const bint &obj) {
len = obj.len;
for(int i = 0;i < 600;++ i) {
data[i] = obj.data[i];
}
}
bint add_zeros2(int n) {
bint tmp;
for(int i = len + n - 1;i >= n;-- i) {
tmp.data[i] = data[i - n];
}
for(int i = 0;i < n;++ i)
tmp.data[i] = '0';
tmp.len = n + len;
return tmp;
}
void add_zeros(int n) {
for(int i = len;i < len + n;++ i)
data[i] = '0';
}
void del_zeros() {
for(int i = len;i < 600;++ i)
data[i] = 0;
}
void init() {
for(int i = 0;i < 600;++ i) data[i] = 0;
}
bint operator=(const bint &obj) {
len = obj.len;
for(int i = 0;i < 600;++ i) {
data[i] = obj.data[i];
}
return *this;
}
bint operator-(bint &obj) {
int L1 = len, L2 = obj.len;
obj.add_zeros(L1 - L2);
bint tmp;
tmp.init();
for(int i = 0;i < len;++ i) tmp.data[i] = '0';
for(int i = 0;i < len;++ i) {
if(data[i] > obj.data[i]) tmp.data[i] += data[i] - obj.data[i];
if(data[i] == obj.data[i]) {
if(tmp.data[i] - '0' == -1) {
tmp.data[i] = '9';
--tmp.data[i + 1];
}
else tmp.data[i] = '0';
}
if(data[i] < obj.data[i]) {
tmp.data[i] += data[i] - obj.data[i] + 10;
tmp.data[i + 1] = -1 + '0';
}
}
obj.del_zeros();
int cnt = 0;
for(int i = len - 1;i >= 0;-- i) {
if(tmp.data[i] == 0) continue;
if(tmp.data[i] == '0') {
tmp.data[i] = 0;
continue;
}
if(tmp.data[i] != '0') {
cnt = i;
break;
}
}
tmp.len = cnt + 1;
tmp.del_zeros();
if(tmp.data[0] == 0) tmp.data[0] = '0';
return tmp;
}
bint operator%(bint &obj) {
int cnt = len - 1;
bint tmp = *this;
for(int i = cnt;i >= 0;-- i) {
bint div = obj.add_zeros2(i);
while(1) {
if(div > tmp) break;
tmp = tmp - div;
}
}
return tmp;
}
bool operator>(const bint &obj) {
if(len > obj.len) return 1;
if(len < obj.len) return 0;
for(int i = len - 1;i >= 0;-- i) {
if(data[i] > obj.data[i]) return 1;
if(data[i] == obj.data[i]) continue;
if(data[i] < obj.data[i]) break;
}
return 0;
}
bool operator==(const bint &obj) {
return (strcmp(data, obj.data) == 0);
}
int div_2() {
int carry = 0;
for(int i = len - 1;i >= 0;-- i) {
int tmp = data[i] - '0';
data[i] = (tmp + carry * 10) / 2 + '0';
carry = tmp % 2;
}
for(int i = len - 1;i >= 0;-- i)
if(data[i] != '0') {
len = i + 1;
break;
}
del_zeros();
return carry;
}
};
istream& operator>>(istream &in, bint &obj) {
obj.init();
char t[600];
in >> t;
obj.len = strlen(t);
for(int i = 0;i < obj.len;++ i)
obj.data[i] = t[obj.len - i - 1];
return in;
}
ostream& operator<<(ostream &os, const bint &obj) {
for(int i = obj.len - 1;i >= 0;-- i)
os << obj.data[i];
}
int main() {
bint t1, t2;
cin >> t1 >> t2;
int ans[2000] = {0};
while(1) {
if(strcmp(t1.data, "0") == 0) break;
if(strcmp(t2.data, "0") == 0) break;
if(t1 > t2) {
t1 = t1 % t2;
continue;
} else if(t1 == t2) break;
else {
t2 = t2 % t1;
continue;
}
}
int cnt = 0;
if(t2 > t1) t1 = t2;
while(1) {
if(strcmp(t1.data, "0") == 0) break;
ans[cnt] = t1.div_2();
++ cnt;
}
bool flag = 0;
for(int i = 1999;i >= 0;-- i) {
if(ans[i] != 0) flag = 1;
if(flag) cout << ans[i];
}
cout << endl;
}
zqy2018's solution
/*
Hint: use Stein algorithm
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
char s1[505], s2[505];
int ss1[2005], ss2[2005];
int tmp[2005];
int rightshift(int* num){
int x = 0;
for (int i = num[0]; i >= 1; --i){
x = num[i] + 10 * x;
num[i] = x >> 1, x %= 2;
}
if (num[0] > 1 && !num[num[0]]) --num[0];
return x;
}
void mminus(int* num1, int* num2){
int x = 0;
for (int i = 1; i <= num2[0]; ++i){
x = 10 + num1[i] - num2[i] + x;
num1[i] = x % 10;
x = x / 10 - 1;
}
for (int i = num2[0] + 1; i <= num1[0]; ++i){
x = 10 + num1[i] + x;
num1[i] = x % 10;
x = x / 10 - 1;
}
while (num1[0] > 1 && num1[num1[0]] == 0) --num1[0];
}
int cmp(int* num1, int* num2){
if (num1[0] != num2[0])
return (num1[0] < num2[0] ? -1: 1);
for (int i = num1[0]; i >= 1; --i)
if (num1[i] != num2[i])
return (num1[i] < num2[i] ? -1: 1);
return 0;
}
void output(int* num){
for (int i = num[0]; i >= 1; --i)
cout << num[i];
cout << endl;
}
void stein(int* num1, int* num2, int& acc){
bool f1 = (num1[1] % 2 == 0), f2 = (num2[1] % 2 == 0);
// output(num1);
// output(num2);
if (f1 && f2){
rightshift(num1), rightshift(num2), ++acc;
stein(num1, num2, acc);
}else if (!f1 && !f2){
mminus(num1, num2);
rightshift(num1);
int res = cmp(num1, num2);
if (res > 0) stein(num1, num2, acc);
else if (res < 0) stein(num2, num1, acc);
}else {
if (f1) rightshift(num1);
else rightshift(num2);
int res = cmp(num1, num2);
if (res > 0) stein(num1, num2, acc);
else if (res < 0) stein(num2, num1, acc);
}
}
void init(){
cin >> s1 >> s2;
int l1 = strlen(s1), l2 = strlen(s2);
for (int i = 0; i < l1; ++i)
ss1[i + 1] = s1[l1 - i - 1] - '0';
for (int i = 0; i < l2; ++i)
ss2[i + 1] = s2[l2 - i - 1] - '0';
ss1[0] = l1, ss2[0] = l2;
while (ss1[0] > 1 && ss1[ss1[0]] == 0) --ss1[0];
while (ss2[0] > 1 && ss2[ss2[0]] == 0) --ss2[0];
}
void solve(){
int acc = 0, res = cmp(ss1, ss2);
if (res > 0) stein(ss1, ss2, acc); // the former is larger
else if (res < 0) stein(ss2, ss1, acc);
int ans_len = 0;
while (ss1[0] > 1 || ss1[1] != 0){
tmp[ans_len++] = rightshift(ss1);
}
for (int i = ans_len - 1; i >= 0; --i)
cout << tmp[i];
for (int i = 0; i < acc; ++i)
cout << '0';
cout << endl;
}
int main(){
init();
solve();
return 0;
}