Skip to content

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;
}