BZOJ 1876: [SDOI2009]SuperGCD – [高精度]


题目传送门(BZOJ)
>原文链接<

题解 :

高精度GCD模板

平时使用的辗转相除, 由于高精度取模太慢了, 到这里并不适用, 我们采用复杂度一样的更相减损法

更相减损的步骤 :

  • 判断两个数是否都是2的倍数, 如果是, 累加(乘)一个2到答案里, 两数同时约2
  • 有一个数是2的倍数 : 只把它约2
  • 用大数减小数, 与原来的小数构成新的两个数, 重复以上过程
  • 发现除以2的次数要比相减的次数多, 复杂度有保证

这样最后得到的一个非0数, 与之前累乘的2再乘一次, 就是最后的答案.

我们只需要实现高精度乘2, 高精度除以2, 高精度减法, 高精度比较大小即可.

注意效率问题, 要压位, 用long long压16位或者int压8位都行, 前者应该快一点? 不过都能过

代码 :

#include 
#include 
#include 
#include 
const int p = 1e8; 
struct INT {
    char w[15100];
    int a[5000], len;
    INT(){memset(a, 0, sizeof a); len = 0;}
    inline int& operator [] (const int cur) {return a[cur];}
    inline const int& operator [] (const int cur) const {return a[cur];}
    inline bool operator < (const INT &b) const {
        if(len != b.len) return len < b.len;
        for(int i = len; i >= 1; i -- ) if(a[i] != b[i]) return a[i] < b[i];
        return false;
    }
    inline void operator -= (const INT &b) {
        for(int i = 1; i <= len; i ++ ) {
            a[i] -= b[i];
            if(a[i] < 0) a[i]+=p, a[i+1] --;
        }
        for(; len && !a[len]; len -- );
    }
    inline void operator *= (const int &x) {
        for(int i = len; i >= 1; i -- ) {
            a[i] <<= 1;
            if(a[i] >= p) a[i+1] += a[i]/p, a[i]-=p;
        }
        if(a[len+1]) ++ len;
    }
    inline void operator /= (const int &x) {
        for(int i = len; i >= 1; i -- ) {
            if(a[i]&1) a[i-1]+=p;
            a[i] >>= 1;
        }
        for(; len && !a[len]; len -- );
    }
    inline bool is0() {return len == 0;}
    inline bool is2() {return a[1] & 1;}
    inline void read() {
        scanf("%s", w+1); int l = strlen(w+1);
        std :: reverse(w+1, w+l+1);
        int now = 0, f = 1;
        for(int i = 1; i <= l; i ++ ) {
            now += f*(w[i]^48);
            if(i%8 == 0) a[++len] = now, now /= p, f = 1;
            else f *= 10;
        }
        if(now) a[++len] = now;
        for(; len && !a[len]; len -- );
    }
    inline void print() {
        printf("%d", a[len]);
        for(int i = len-1; i >= 1; i -- ) printf("%08d", a[i]);
        putchar('\n');
    }
    inline void gcd(INT &b) {
        int f = 0;
        while(!is0()&&!b.is0()) {
            while(!is2()  &&!b.is2()) ++ f, *this /= 2, b /= 2;
            while(!is2()  ) *this /= 2;
            while(!b.is2()) b /= 2;
            if(b < *this) std :: swap(b, *this);
            b -= *this;
        }
        if(is0()) *this = b;
        while(f -- ) *this *= 2;
    }
}a, b;
int main() {
    a.read(), b.read();
    a.gcd(b);
    a.print();
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注