Editorial for ptit012: Thế nào là tràn số?

Hiểu bài toán

Bài toán yêu cầu tính và in ra ba phép toán cộng (+), trừ (-), và nhân () của hai số nguyên dương a và b. Dữ liệu đầu vào gồm hai số a và b, mỗi số có giá trị từ 1 đến 210^9. Kết quả cần được in ra trên một dòng, cách nhau bởi dấu cách.

Về mặt phạm vi giá trị:

• Phép cộng: a + b có thể lên tới 4*10^9 (vượt quá giới hạn của kiểu int 32-bit).
• Phép trừ: a - b (với a >= b) luôn không âm và không vượt quá 2*10^9.
• Phép nhân: a * b có thể lên tới 4*18 (vượt quá rất nhiều so với kiểu int 32-bit và cả kiểu long long 64-bit trên một số hệ thống).

Tuy nhiên, dựa vào các solution nộp vào, long long (64-bit) có vẻ là đủ để xử lý các phép toán này trong phạm vi đề bài, nhưng để an toàn tuyệt đối với số lớn (đặc biệt là phép nhân), việc sử dụng số lớn (Big Integer) là phương pháp chuẩn mực nhất.

Các cách tiếp cận

Cách Sử dụng biến kiểu long long (C/C++)

#include <stdio.h>
#define ll long long

int main(){
    ll a, b;
    scanf("%lld %lld", &a, &b);
    printf("%lld %lld %lld", a + b, a - b, a * b);
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là cách tiếp cận đơn giản nhất.

1. Kiểu dữ liệu: Sử dụng kiểu long long (hoặc __int64) để lưu trữ số nguyên. long long thường có kích thước 64-bit, cho phép lưu trữ số nguyên trong khoảng -910^18 đến 910^18.
2. Phép tính:
   • a + b: Tối đa ~4*10^9, nằm trong giới hạn.
   • \a - b: Tối đa ~2*10^9, nằm trong giới hạn.
   • a * b: Tối đa ~410^18. Giới hạn trên của long long là khoảng 9.210^18. Vì vậy, phép nhân này vẫn an toàn và không bị tràn số.
3. I/O: Dùng scanf và printf với định dạng %lld để đọc và ghi kiểu long long.

Phương pháp này hiệu quả, ngắn gọn và giải quyết được bài toán trong các ràng buộc dữ liệu đầu vào.

Cách Xử lý số lớn (Big Integer) bằng chuỗi

// Hàm cộng hai chuỗi số lớn
void add(char a[], char b[]) {
    // Logic cộng từng chữ số từ phải sang trái, nhớ nhớ
}

// Hàm trừ hai chuỗi số lớn (a >= b)
void subtract(char a[], char b[]) {
    // Logic trừ từng chữ số từ phải sang trái, mượn số
}

// Hàm nhân hai chuỗi số lớn
void multiply(char a[], char b[]) {
    // Logic nhân từng chữ số, lưu vào mảng trung gian, rồi xử lý số nhớ
}

int main() {
    char s1[200], s2[200];
    scanf("%s %s", s1, s2);
    add(s1, s2);
    printf(" ");
    subtract(s1, s2);
    printf(" ");
    multiply(s1, s2);
    return 0;
}

• Time Complexity: O(N * M) ~ O(20)
• Space Complexity: O(N * M) ~ O(400)

Đây là phương pháp tổng quát nhất để giải quyết bài toán với số lớn, đảm bảo không bao giờ bị tràn số kể cả khi a và b lớn hơn rất nhiều.

1. Lưu trữ: Hai số được nhập dưới dạng chuỗi ký tự (mảng ký tự).
2. Phép cộng:
   • Duyệt từ chữ số cuối cùng lên đầu tiên của hai chuỗi.
   • Cộng từng cặp chữ số tương ứng cùng với giá trị nhớ (carry).
   • Nếu tổng vượt quá 9, giữ lại phần dư và cộng 1 vào nhớ cho bước tiếp theo.
3. Phép trừ:
   • Tương tự cộng nhưng là trừ.
   • Xử lý trường hợp mượn số (borrow) khi số bị trừ nhỏ hơn số trừ.
   • Vì a, b > 0 và không có yêu cầu âm, ta chỉ cần xử lý khi a >= b (hoặc đổi chỗ nếu a < b và thêm dấu trừ, nhưng đề bài chỉ ghi a, b dương và a-b nên a có thể lớn hơn b).
4. Phép nhân:
   • Sử dụng giải thuật nhân từng chữ số (như nhân tay).
   • Tạo một mảng kết quả có độ dài len(a) + len(b).
   • Duyệt qua từng chữ số của a và b, nhân và cộng vào vị trí tương ứng trong mảng kết quả.
   • Cuối cùng, xử lý các số nhớ.

Độ phức tạp thời gian là O(N*M) với N, M là độ dài chuỗi. Vì N, M rất nhỏ (khoảng 10), phương pháp này chạy cực nhanh.

Cách Sử dụng kiểu dữ liệu 128-bit (__int128)

#include <stdio.h

int main() {
    long long a, b;
    scanf("%lld %lld", &a, &b);
    __int128 res = (__int128)a * b;
    printf("%lld %lld %lld\n", (long long)(a+b), (long long)(a-b), (long long)res);
    // Lưu ý: In trực tiếp __int128 cần hàm in tùy chỉnh
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Một số trình biên dịch modern (như GCC, Clang) hỗ trợ kiểu số nguyên 128-bit (__int128).

1. Kiểu dữ liệu: __int128 cho phép lưu trữ số nguyên lên tới 2^128 - 1 (~3.4 * 10^38), đủ lớn để chứa kết quả nhân 4*10^18.
2. Hạn chế: Kiểu __int128 không được hỗ trợ bởi hàm printf chuẩn. Để in ra, cần ép kiểu về long long (nếu kết quả nhỏ hơn 2^63) hoặc viết hàm in tùy chỉnh.

Phương pháp này hiệu năng cao nhất (O(1)) nhưng phụ thuộc vào môi trường biên dịch.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Phép nhân là phép toán có nguy cơ tràn số cao nhất (4*10^18), cần kiểm tra kỹ giới hạn kiểu dữ liệu.
• Kiểu long long (64-bit) là đủ cho các ràng buộc đề bài này.
• Phương pháp chuỗi (Big Integer) là phương pháp an toàn nhất cho các bài toán yêu cầu xử lý số nguyên rất lớn (không giới hạn).

Lỗi thường gặp

• Sử dụng kiểu int (32-bit)导致 tràn số ở phép cộng và chắc chắn tràn số ở phép nhân.
• Quên xử lý số nhớ (carry) hoặc mượn số (borrow) khi viết hàm thủ công.
• Lỗi in/out: Sử dụng sai định dạng (%d thay vì %lld) cho kiểu long long.