SDOI2009_SuperGCD|题解

SDOI2009_SuperGCD|题解

九月 04, 2018

一道恶心人的毒瘤题:高精度gcd

注意到,在高精度运算中取模是通过重复相减实现的

所以对于高精度gcd,辗转相除法和更相减损术是一样的

那档燃是写更相减损术

这毒瘤题还卡常,所以就搞了几个小把戏:

  1. 把高精度减法直接重载为-=
  2. 采取亿进制(事实上甚至可以写成万亿进制)

不得不说高精度运算是很坑的算法,建议除了构造函数和重载赋值符之外所有成员函数都应该用const修饰

以及亿进制下的输出也是一个很麻烦的事情…

代码如下


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <ctime>
#define LL long long
using namespace std;
struct big_int{
        LL data[25000],len;
        big_int(char *al){
                LL al_len = strlen(al),base = 1;
                data[len = 0] = 0;
                for (LL p = al_len - 1;p >= 0;p --){
                        if (base >= 100000000)
                                ++ len,data[len] = 0,base = 1;
                        data[len] += (al[p] - '0') * base;
                        base *= 10;
                }
                len ++;
                return ;
        }
        void print()const{
                LL len = this->len;
                if (!len) {
                        cout <<"0\n";
                        return ;
                }
                len --;
                LL b = 10000000;
                while((data[len] / b) == 0)
                        b /= 10;
                printf("%lld",data[len]);
                string out = "";
                for (LL i = len - 1;i >= 0;-- i){
                        LL b = 10000000,d = data[i];
                        while(b){
                                out += d / b + '0';
                                d %= b;
                                b /= 10;
                        }
                }
                cout << out << endl;
                return ;
        }
        bool operator < (const big_int &al)const{
                if (len != al.len)
                        return len < al.len;
                for (LL i = len - 1;i >= 0;-- i)
                        if (data[i] != al.data[i])
                                return data[i] < al.data[i];
                return 0;
        }
        big_int operator -= (big_int &al){
                for (LL i = 0;i < al.len;++ i)
                        data[i] -= al.data[i];
                for (LL i = 0;i < len;++ i)
                        if (data[i] < 0)
                                data[i] += 100000000,
                                data[i + 1] -= 1;
                while (data[-- len] == 0 && len > 0);
                len ++; 
                if (len == 1 && data[0] == 0)
                        len = 0;
                return *this;
        }
};
LL low_gcd(LL a,LL b){
        return b?low_gcd(b,a % b):a;
}
int main(){
        char alpha[20000],beta[20000];
        scanf("%s%s",alpha,beta);
        if (strlen(alpha) <= 18 && strlen(beta) <= 18){
                LL al,be;
                sscanf(alpha,"%lld",&al);
                sscanf(beta ,"%lld",&be);
                cout << low_gcd(al,be);
        }
        else{
                big_int al = big_int(alpha),be = big_int(beta);
                while (al < be || be < al){
                        if (be < al)
                                al -= be;
                        else
                                be -= al;
                }
                al.print();
        }
        return 0;
}

文结