Hướng dẫn cho Tổng hiệu

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

$\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}$

$\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}$

$\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}$

$\color{orange}{\text{Hint 1 <Formula>}}$

Gọi $T = A + B$ và $H = A - B$

Ta có $A = \frac{(A + B)\ +\ (A - B)}{2} = \frac{T + H}{2}$

Ta có $B = \frac{(A + B)\ -\ (A - B)}{2} = \frac{T - H}{2}$

$\color{orange}{\text{Hint 2 <Bignum>}}$

Vì bài này giới hạn lớn nên ta phải xử lí số lớn ($bignum$)

Các phép toán đều cơ bản như toán cấp 1, cụ thể trong bài này ta cần 3 phép: $+$, $-$, $\div$

Các phép tính được thực hiện tuần tự từng chữ số trái sang phải hoặc phải sang trái

$\color{goldenrod}{\text{Approach}}$

$\color{brown}{\text{Lưu ý}}$

Bài này có nhiều cách để biểu diễn tùy theo mỗi người

Xong dưới đây mình xin biểu diễn bằng vector chữ số để tính toán tốt hơn và nhanh hơn

Mình dưới đây giải thích nhiều lệnh, nhưng có thể có chỗ mình ngộ nhận mà không nói kĩ, có chỗ mình nói quá chi tiết dù dễ nhận thấy

Nếu có chỗ nào giải thích chưa được rõ, các bạn cứ comment bên dưới mình giải thích chi tiết hơn

Editorial này sẽ được update liên tục để đưa tới code tối ưu nhất

Mình có cách optimize hơn nhưng nó khá là dài để giải thích hết, nên mình sài tạm code mình AC lúc thi để nói

Có những câu lệnh mà bạn có thể tùy chỉnh nó riêng cho mình

Ví dụ trong này mình có sài lệnh getString(s) là $fast-input$ cho xâu $s$ (chỉ cần chữ số và dấu)

$\color{brown}{\text{Cơ sở bignum}}$

Đầu tiên mình cần quan tâm bignum có những gì:

Dấu của số sẽ được lưu trong biến boolean $bignum.sign$
Từng chữ số sẽ được lưu vào một mảng vector $bignum.value$
Ban đầu ta khởi tạo bằng 0 nên $sign = false$ và $value = {0}$

C++

struct bignum {
    bool sign = false;
    vector<int> value = {0};
};

Để cho tiện trong việc tính toán, ta sẽ lưu trữ mảng các chữ số theo thứ tự từ trái qua phải

Khi cộng, trừ, nhân, ... ra số to hơn, ta chỉ cần chèn các chữ số sang bên phải $vector$ $O(1)$ thay vì chèn trái $O(bignum.size)$
Khi cộng, trừ, chia, ... ra số nhỏ hơn ta sẽ tính toán dần từ phải qua trái và loại bỏ phần thừa ở bên phải

Để tính nhanh hơn trong tính toán, ta sẽ sử dụng kiểu dữ liệu $int$ và tính toán từng cụm chữ số

Mỗi khi tính toán $compiler$ thường chuyển kiểu dữ liệu về $int$ nên đỡ mất công chuyển ([1] mình add reference sau)
Khi tính toán, compiler nếu tính cả số thì nhanh hơn là tính từng chữ số, nên ta sẽ tính từng cụm chữ số một ([2] mình add reference sau)
Để tránh lỗi ngu ngốc và tràn số trong quá trình code bignum, mà cũng vì nó khá phức tạp và dễ sai

Nên mình sẽ đặt giá trị vừa đủ để bình phương max của từng cụm chữ số sẽ không vượt quá kiểu dữ liệu $int$

C++

const int BASE = 1e4; /// giá trị các số nằm trong khoảng %BASE <=> [0...BASE)
const int DIGIT = 4;  /// một cụm chữ số gồm 4 chữ số

$\color{brown}{\text{Phép nhận bignum}}$

Phép nhập mình cần nhận dữ liệu là string từ file input -> mảng chữ số $bignum.value$

Chúng ta sẽ nhận từ $cin >>$ nên ta sẽ làm một operator như sau

C++

istream& operator >> (istream& cin,  bignum &N) {
    ...
    return cin;
}

Như đã nói thì chúng ta sẽ nhận dữ liệu kiểu xâu, nên mình sẽ nhận vào $string\ s$

C++

istream& operator >> (istream& cin,  bignum &N) {
    string s;
    getString(s); /// Nhan xau nhanh: {'-'} va ['0'..'9']

    ...
    return cin;
}

Bignum có thể là số âm, nên ta xử lí trước phần đó

Khởi tạo $sign = false$ (luc dau khong co dau)
Mỗi khi nhận dấu trừ, ta sẽ đổi dấu bằng $sign = !sign$
Vì phép xóa đầu $string$ có đpt $O(n)$, mà các dấu '-' không ảnh hưởng tới $bignum.value$

Ta sẽ dùng biến $p$ để duyệt các dấu '-'

Với $s[0]..s[p - 1]$ là các dấu '-'

Và $s[p]..s[s.size - 1]$ là các chữ số

C++

istream& operator >> (istream& cin,  bignum &N) {
    string s;
    getString(s); /// Nhan xau nhanh: {'-'} va ['0'..'9']

    N.sign = false; /// Luc dau khong co dau
    int p = 0;      /// Vi tri goc
    while (p + 1 < int(s.size()) && s[p] == '-') /// Duyet cac dau '-'
        N.sign = !N.sign, p++;              /// s[0]..s[p-1] la dau '-'

    ...
    return cin;
}

Khi nhận giá trị vào từng cụm từ bên phải sang trái

Mỗi cụm ta lưu được $DIGIT$ chữ số, nên tối đa lưu được $\lfloor \frac{s.size}{DIGIT} \rfloor$ cụm đủ $DIGIT$ chữ số
Còn cụm còn lại, là cụm chữ số ở đầu $bignum$ là vị trí cuối của $bignum.value$
Ta khởi tạo $bignum.value$ bằng độ dài tối đa của nó là $\lfloor \frac{s.size}{DIGIT} \rfloor + 1$ với các giá trị $0$
Vì ta duyệt xâu $s$ và $bignum.value$ ngược nhau nên $i$ tương ứng với vị trí đối xứng là $s.size - i - 1$
Từ đó: Vị trí chữ số $s_i$ trong $bignum.value$ là $pos = \lfloor \frac{s.size - i - 1}{DIGIT} \rfloor$

Khi chèn giá trị $d$ vào bên phải một cụm chữ số $x$

Lưu ý chữ số $s_i$ là chữ số kiểu kí tự, $d$ là chữ số kiểu số nguyên
Ta có $d = s_i - '0'$
Trong mỗi cụm $x$, có $new\_x = 10 * x + d$
Vì dụ $d = 2$ và $x = 27$, ta muốn có "27" + "2" = "272" thì ta làm "272 = 10 * x + d = 270 + 2$
Nên ta dùng phép $x = 10 * x + d$ để chèn vào bên phải cùng

C++

istream& operator >> (istream& cin,  bignum &N) {
    string s;
    getString(s); /// Nhan xau nhanh: {'-'} va ['0'..'9']

    N.sign = false; /// Luc dau khong co dau
    int p = 0;      /// Vi tri goc
    while (p + 1 < int(s.size()) && s[p] == '-') /// Duyet cac dau '-'
        N.sign = !N.sign, p++;              /// s[0]..s[p-1] la dau '-'

    N.value.assign(s.size() / DIGIT + 1, 0); /// Khoi tao gia tri
    for (int i = p; i < sz(s); ++i) {        /// s[p]..s[s.size - 1] la chu so
        int pos = (s.size() - i - 1) / DIGIT; /// Tim vi tri
        N.value[pos] = (10 * N.value[pos]) + (s[i] - '0'); /// x = 10 * x + d
    }

    ...
    return cin;
}

Nhận thấy rằng mình có thể nhận các giá trị sai

Khi có cụm chữ số vượt giá trị $max = BASE - 1$ (xem lại ở trên)
Ví dụ: $s = "100002702" \Rightarrow N.value = {2702, 10000}$
Khi có các chữ số đứng ở đầu
Ví dụ: $s = "000002702" \Rightarrow N.value = {2702, 0}$

Để sửa được số này thành các giá trị đúng, ta sẽ dùng hàm fix vector như sau

Nhận xét rằng sau khi fix số, cùng lắm số có thêm 1 cụm chữ số mới chứa một chữ số
Vì thế để tiện tính toán, ta nhét thêm số 0 vào cuối
Duyệt với mỗi phần tử, trừ phần tử được thêm vào trước đó

Ta sẽ tăng giá trị cho cụm sau "{.., 12702,..} -> {.., 2702, 1,..}"

Ta sẽ điều chỉnh giá trị hiện tại thuộc [0..BASE)

Tuy nhiên, sau quá trình tính toán trên, nếu có cụm $x$ âm, ta xử lí nó

Ta sẽ điều chỉnh nó lên [0..BASE) bằng cách thêm $BASE$ vào $x$ và giảm 1 đi cụm sau (mượn BASE từ cụm sau)

C++

istream& operator >> (istream& cin,  bignum &N) {
    string s;
    getString(s); /// Nhan xau nhanh: {'-'} va ['0'..'9']

    N.sign = false; /// Luc dau khong co dau
    int p = 0;      /// Vi tri goc
    while (p + 1 < int(s.size()) && s[p] == '-') /// Duyet cac dau '-'
        N.sign = !N.sign, p++;              /// s[0]..s[p-1] la dau '-'

    N.value.assign(s.size() / DIGIT + 1, 0); /// Khoi tao gia tri
    for (int i = p; i < sz(s); ++i) {        /// s[p]..s[s.size - 1] la chu so
        int pos = (s.size() - i - 1) / DIGIT; /// Tim vi tri
        N.value[pos] = (10 * N.value[pos]) + (s[i] - '0'); /// x = 10 * x + d
    }

    N.value.push_back(0); /// De tien tinh toan
    for (int i = 0; i + 2 < N.value.size(); ++i) {
        N.value[i + 1] += N.value[i] / BASE; /// Them gia tri cho cum sau
        N.value[i] %= BASE;                  /// Dieu chinh gia tri cum hien tai
        if (N.value[i] < 0) {   /// Cum x am
            N.value[i] += BASE; /// Dieu chinh gia tri x
            N.value[i + 1]--;   /// Giam gia tri cum sau
        }
    }
    while (a.size() >= 2 && a.back() == 0) a.pop_back(); /// Loai bo gia tri vo nghia o dau

    ...
    return cin;
}

Để cho gọn việc tính toán, ta sẽ nhét một số đoạn code vào thành hàm

C++

void fix(vector<int> &a) {
    a.push_back(0); /// De tien tinh toan
    for (int i = 0; i + 2 < a.size(); ++i) {
        a[i + 1] += a[i] / BASE; /// Them gia tri cho cum sau
        a[i] %= BASE;            /// Dieu chinh gia tri cum hien tai
        if (a[i] < 0) {   /// Cum x am
            a[i] += BASE; /// Dieu chinh gia tri x
            a[i + 1]--;   /// Giam gia tri cum sau
        }
    }
    while (a.size() >= 2 && a.back() == 0) a.pop_back(); /// Loai bo gia tri vo nghia o dau
}

void str_tovi(bool &sign, vector<int> &value) {
    string s;
    getString(s); /// Nhan xau nhanh: {'-'} va ['0'..'9']

    sign = false; /// Luc dau khong co dau
    int p = 0;      /// Vi tri goc
    while (p + 1 < int(s.size()) && s[p] == '-') /// Duyet cac dau '-'
        sign = !sign, p++;              /// s[0]..s[p-1] la dau '-'

    value.assign(s.size() / DIGIT + 1, 0); /// Khoi tao gia tri
    for (int i = p; i < sz(s); ++i) {        /// s[p]..s[s.size - 1] la chu so
        int pos = (s.size() - i - 1) / DIGIT; /// Tim vi tri
        value[pos] = (10 * value[pos]) + (s[i] - '0'); /// x = 10 * x + d
    }
    fix(value);
}

istream& operator >> (istream& cin,  bignum &N) {
    str_tovi(N.sign, N.value);

    ...
    return cin;
}

Lưu ý trong trường hợp $bignum = 0$ ta sẽ xóa dấu của nó như sau

C++

istream& operator >> (istream& cin,  bignum &N) {
    str_tovi(N.sign, N.value);
    if (N.value.size() == 1) /// Neu bignum chi co 1 cum chu so
        if (N.value.front() == 0) /// Neu cum chu so do la 0
            N.sign = false;

    return cin;
}

$\color{brown}{\text{Phép xuất bignum}}$

Phép xuất mình cần xuất dữ liệu là mảng chữ số $bignum.value$ -> string ra file output

Chúng ta sẽ nhận từ $cout <<$ nên ta sẽ làm một operator như sau

C++

ostream& operator << (ostream& cout, bignum  N) {
    ...
    return cout;
}

Đầu tiên, nếu số đó có dấu thì mình xuất ra

Nhưng mình phải kiểm tra nếu $bignum = 0$ thì không in ra dấu trừ

$bignum \neq 0 \Leftrightarrow bignum$ có nhiều cụm chữ số, hoặc giá trị của cụm duy nhất $\neq 0$

C++

ostream& operator << (ostream& cout, bignum  N) {
    if (N.sign == true)  /// Neu bignum co dau
        if (sz(N.value) > 1 || N.value.front() > 0) /// Neu bignum khac 0
            cout << '-'; /// In ra dau am

    ...
    return cout;
}

Mình xuất từ cuối mảng về

Chỉ có cụm cuối mảng ta xuất bình thường
Các cụm khác, nếu nó không đủ chữ số, ta chèn thêm số 0 vào phía trước

Dùng "printf()" để code gọn hơn như dưới

C++

ostream& operator << (ostream& cout, bignum  N) {
    if (N.sign && (sz(N.value) > 1 || N.value.front() > 0)) printf("-");

    printf("%d", N.value.back());
    for (int i = int(N.value.size()) - 2; i >= 0; --i)
        printf("%0*d", DIGIT, N.value[i]);
    return cout;
}

Hoặc nếu bạn thích thuần "cout <<"

C++

string int_tostr(int x, int form = 0) {
    string res;
    if (form) { 
        do res += char(x % 10 + '0');       /// Chen tung chu so vao
        while ((sz(res) < form) && (x /= 10)); /// den khi khong duoc them nua
        res += string(form - sz(res), '0'); /// Chen them so 0 vao dau
    }
    else do res += char(x % 10 + '0'); while (x /= 10); /// Chen tat ca chu so vao
    reverse(all(res)); /// ta nhan tu phai qua nen dao nguoc lai
    return res;
}

ostream& operator << (ostream& cout, bignum  N) {
    if (N.sign == true)  /// Neu bignum co dau
        if (sz(N.value) > 1 || N.value.front() > 0) /// Neu bignum khac 0
            cout << '-'; /// In ra dau am

    cout << int_tostr(N.value.back());
    for (int i = int(N.value.size()) - 2; i >= 0; --i)
        cout << int_tostr(N.value[i], DIGIT);
    return cout;
}

$\color{brown}{\text{Phép cộng bignum}}$

C++

bignum operator + (bignum a, bignum b) {
    /// somehow: a += b;

    ...
    return a;
}

Trường hợp 2 số cùng dấu

Tổng của hai số cũng cùng dấu với hai số
Nên ta chỉ cần cộng giá trị 2 vector a, b

Lưu ý, khi ta cộng b vào a, có thể xâu kết quả lớn hơn, nên ta resize sang max_size 2 số

Duyệt mọi giá trị $b.value[i]$ thêm vào $a.value[i]$ sau đó ta fix lại số là xong

C++

bignum operator + (bignum a, bignum b) {
    int n = max(a.value.size(), b.value.size()); /// lay max_size
    if (a.sign == b.sign) /// hai so cung dau
    {
        a.value.resize(n);
        for (int i = 0; i < int(b.value.size()); ++i)
            a.value[i] += b.value[i];

        fix(a);
    }
    else
    {
        ...
    }

    return a;
}

Trường hợp 2 số khác dấu

Để tiện tính toán, ta mặc định a là số dương, b là số âm

Đơn giản là ta đảo dấu 2 (a <-> b) khi $a$ âm

Lưu ý rằng ta đang tính toán trên $a$, nên lát phải trả lại dấu ban đầu

Đơn giản là ta dùng biến boolean $flip$ để đảo lại dấu khi cần

C++

    else
    {
        bool flip = a.sign;
        if (flip) swap(a.sign, b.sign);
        ...
        if (flip) swap(a.sign, b.sign);
    }

Sau đó chúng ta sẽ so sánh giá trị 2 số

Vì $a(+), b(-)$ nên khi $b > a$, ta sẽ đảo dấu kết quả

Sau đó ta chỉ việc tính toán 2 số như cách trên

C++

    else
    {
        bool flip = a.sign;
        if (flip) swap(a.sign, b.sign);
        if (compare(b < a) == true) /// <---------------------
        {
            flip = !flip;
            swap(a.value, b.value);
        }

        a.value.resize(n);
        for (int i = 0; i < int(b.value.size()); ++i)
            a.value[i] -= b.value[i];

        fix(a.value);
        if (flip) swap(a.sign, b.sign);
    }
}

Việc kiểm tra giá trị 2 số hơn bé nhau ta làm như sau

Nếu độ dài 2 số khác nhau:

Gọi $intsize(x)$ trả về độ dài của $x$ $\Leftrightarrow intsize(x) = \lfloor \log_{10}(x) \rfloor$

Dễ tính được $size(a) = intsize(a.value.back) + (a.value.size() - 1) \times DIGIT$

$(size(a) > size(b)) \Rightarrow return\ +1$;

$(size(a) > size(b)) \Rightarrow return\ -1$;

Ngược lại, nếu khi duyệt từ phải qua tồn tại một vị trí mà 2 giá trị khác nhau

$(a[i] > b[i]) \Rightarrow return\ +1$;

$(a[i] < b[i]) \Rightarrow return\ -1$;

Ngược lại, ta có $a = b \Rightarrow return\ 0;$

C++

inline int intsz(int x) {
         if (x >= 1e9) return 10;
    else if (x >= 1e8) return  9;
    else if (x >= 1e7) return  8;
    else if (x >= 1e6) return  7;
    else if (x >= 1e5) return  6;
    else if (x >= 1e4) return  5;
    else if (x >= 1e3) return  4;
    else if (x >= 1e2) return  3;
    else if (x >= 1e1) return  2;
    else if (x >= 1e0) return  1;
}

/// -1: a < b
///  0: a = b
/// +1: a > b
inline int compare(const vi a, const vi b) {
    int n = intsz(a.back()) + (sz(a) - 1) * DIGIT;
    int m = intsz(b.back()) + (sz(b) - 1) * DIGIT;
    if (n != m) return (n < m) ? -1 : +1;

    for (int i = n - 1; i >= 0; --i)
        if (a[i] != b[i]) return (a[i] < b[i]) ? -1 : +1;

    return 0;
}

Cuối cùng ta được

C++

bignum operator + (bignum a, bignum b) {
    int n = max(sz(a.value), sz(b.value));
    if (a.sign == b.sign)
    {
        a.value.resize(n);
        for (int i = 0; i < int(b.value.size()); ++i)
            a.value[i] -= b.value[i];
    }
    else
    {
        bool flip = a.sign;
        if (flip) swap(a.sign, b.sign);

        /// -1: a < b
        ///  0: a = b
        /// +1: a > b
        if (compare(a.value, b.value) == -1) /// a < b
        {
            flip = !flip;
            swap(a.value, b.value);
        }

        a.value.resize(n);
        for (int i = 0; i < int(b.value.size()); ++i)
            a.value[i] -= b.value[i];

        if (flip) swap(a.sign, b.sign);
    }

    fix(a.value);
    return a;
}

$\color{brown}{\text{Phép trừ bignum}}$

C++

bignum operator - (bignum a, bignum b) {
    /// somehow: a -= b;

    ...
    return a;
}

Nhận thấy ta cũng chỉ làm theo cách trên với $b$ khác dấu

C++

bignum operator - (bignum a, bignum b) {
    b.sign = !b.sign;
    return a + b;
}

$\color{brown}{\text{Phép chia bignum}}$

Tính toán như toán cấp 1

$$$
142702 │ 2
───────┼───
1 │ 071351
0 │
0 │
1 │
0 │
0 │

digit 1, old_remainder = 0 -> value = 1 -> new_remainder = 1, divisor_value = 0
digit 4, old_remainder = 1 -> value = 14 -> new_remainder = 0, divisor_value = 07
digit 2, old_remainder = 0 -> value = 2 -> new_remainder = 0, divisor_value = 071
digit 7, old_remainder = 0 -> value = 7 -> new_remainder = 1, divisor_value = 0713
digit 0, old_remainder = 1 -> value = 10 -> new_remainder = 0, divisor_value = 07135
digit 2, old_remainder = 0 -> value = 2 -> new_remainder = 0, divisor_value = 071351
fix(value) = 71351
$$$

Nếu chữ số hiện tại lẻ, thì cộng thêm BASE cho cụm sau

Ví dụ {$.., prex, x, ...$} $\Rightarrow$ {$.., prex + BASE, x - 1, ...$}

Ví dụ {$.., 1702, 13, ...$} $\Rightarrow$ {$.., 2702, 12, ...$}

Sau đó ta chia 2 số hiện tại là ra

C++

void div2(vi &a) {
    for (int i = int(a.size()) - 1; i >= 0; --i) {
        if (i > 0)
            if (a[i] % 2 == 1)
                a[i - 1] += BASE;

        a[i] /= 2;            
    }
    fix(a);
}

Nếu ai muốn bitwise

C++

void div2(vi &a) {
    for (int i = int(a.size()) - 1; i >= 0; --i) {
        if (i && (a[i] & 1))
            a[i - 1] += BASE;

        a[i] >>= 1;            
    }
    fix(a);
}

$\color{brown}{\text{Hàm main()}}$

C++

int main()
{
    bignum t, h;
    cin >> t >> h;
    /// t = (a + b)
    /// h = (a - b)
    /// a = (t + h) / 2
    /// b = (t - h) / 2
    bignum a2 = t + h;
    bignum b2 = t - h;
    div2(a2.value);
    div2(b2.value);
    cout << a2 << eol;
    cout << b2 << eol;
    return 0;
}

Bình luận

0

SPyofgame 3:24 p.m. 28 Tháng 6, 2020

Không biết mình giải thích vậy dễ hiểu không hay phải chỉ rõ nguyên lí mấy hàm kia hoạt động nhỉ

9 bình luận nữa

Hướng dẫn cho Tổng hiệu

\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Formula>}}\)

\(\color{orange}{\text{Hint 2 <Bignum>}}\)

\(\color{goldenrod}{\text{Approach}}\)

\(\color{brown}{\text{Lưu ý}}\)

\(\color{brown}{\text{Cơ sở bignum}}\)

\(\color{brown}{\text{Phép nhận bignum}}\)

\(\color{brown}{\text{Phép xuất bignum}}\)

\(\color{brown}{\text{Phép cộng bignum}}\)

\(\color{brown}{\text{Phép trừ bignum}}\)

\(\color{brown}{\text{Phép chia bignum}}\)

\(\color{brown}{\text{Hàm main()}}\)

Bình luận