最大公约数

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2884 字
给定两个不超过10^3000位的正整数A,B
一本通
例
正文

/*
原题：T1627「一本通 6.3 例 3」最大公约数
题意：给定两个不超过 10^3000 位的正整数 A,B，输出它们的最大公约数。
思路：用压位大整数（基 1e9）存放大数，采用二进制 GCD（Stein 算法），仅用移位与减法，避免大数除法。
复杂度：时间 O(位数^2) / 空间 O(位数)
易错点：基非 2 的幂，右移/左移需按位借位与进位；减法要保证被减数不小于减数。
*/
#include <bits/stdc++.h>
using namespace std;
const long long BASE=1000000000;
struct Big{
    vector<int> d; // 小端，d[0] 最低位，基 1e9
    Big(){
        d.push_back(0);
    }
    Big(const string& s){
        int n=(int)s.size();
        for(int i=n;i>0;i-=9){
            int st=max(0, i-9);
            d.push_back(stoi(s.substr(st, i-st)));
        }
        if(d.empty()) d.push_back(0);
        normalize();
    }
    void normalize(){
        while(d.size()>1 && d.back()==0) d.pop_back();
    }
    bool isZero() const{
        return d.size()==1 && d[0]==0;
    }
    bool isEven() const{
        return (d[0]&1)==0;
    }
    // 返回 -1/0/1
    int cmp(const Big& o) const{
        if(d.size()!=o.d.size()) return d.size()<o.d.size()?-1:1;
        for(int i=(int)d.size()-1;i>=0;i--){
            if(d[i]!=o.d[i]) return d[i]<o.d[i]?-1:1;
        }
        return 0;
    }
    // 除以 2（向下取整）
    void shr1(){
        long long carry=0;
        for(int i=(int)d.size()-1;i>=0;i--){
            long long cur=d[i]+carry*BASE;
            d[i]=(int)(cur/2);
            carry=cur%2;
        }
        normalize();
    }
    // 乘以 2
    void shl1(){
        long long carry=0;
        for(int i=0;i<(int)d.size();i++){
            long long cur=(long long)d[i]*2+carry;
            d[i]=(int)(cur%BASE);
            carry=cur/BASE;
        }
        if(carry) d.push_back((int)carry);
    }
    // 乘以 2^k
    void shlk(int k){
        for(int i=0;i<k;i++) shl1();
    }
    // *this -= o，要求 *this >= o
    void subFrom(const Big& o){
        int borrow=0;
        for(int i=0;i<(int)d.size();i++){
            long long x=d[i]-borrow;
            if(i<(int)o.d.size()) x-=o.d[i];
            if(x<0){
                x+=BASE;
                borrow=1;
            }else{
                borrow=0;
            }
            d[i]=(int)x;
        }
        normalize();
    }
    string toStr() const{
        if(isZero()) return "0";
        char buf[16];
        sprintf(buf, "%d", d.back());
        string res=buf;
        for(int i=(int)d.size()-2;i>=0;i--){
            sprintf(buf, "%09d", d[i]);
            res+=buf;
        }
        return res;
    }
};
Big bgcd(Big a, Big b){
    if(a.isZero()) return b;
    if(b.isZero()) return a;
    int k=0;
    while(a.isEven() && b.isEven()){
        a.shr1();
        b.shr1();
        k++;
    }
    while(a.isEven()) a.shr1();
    while(true){
        while(b.isEven()) b.shr1();
        if(b.cmp(a)<0) swap(a, b);
        b.subFrom(a);
        if(b.isZero()) break;
    }
    a.shlk(k);
    return a;
}
int main(){
    string A, B;
    cin>>A>>B;
    Big a(A), b(B);
    Big g=bgcd(a, b);
    cout<<g.toStr()<<"\n";
    return 0;
}
最大公约数

正文

一本通·提高篇的其它内容
