Editorial for ptit033: Số chia hết hay không?

Hiểu bài toán

Bài toán yêu cầu kiểm tra một số n có chia hết cho hai số a và b hay không dựa trên các trường hợp:

• Nếu chia hết cho cả a và b: in ra 'Co, tat ca!'
• Nếu chỉ chia hết cho a: in ra 'Chi chia het cho a,'
• Nếu chỉ chia hết cho b: in ra 'Chi chia het cho b.'
• Nếu không chia hết cho số nào: in ra 'Khong chia het cho so nao ca.' Input gồm 3 số nguyên dương n, a, b (1 ≤ n, a, b ≤ 10^18).

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

Cách Sử dụng biến kiểu int

#include<stdio.h>

int main(){
    int n,a,b;
    scanf("%d%d%d",&n,&a,&b);
    if (n % a == 0 && n % b == 0) printf("Co, tat ca!");
    else if (n % a == 0 && n % b != 0) printf("Chi chia het cho %d,",a);
    else if (n % a != 0 && n % b == 0) printf("Chi chia het cho %d.",b);
    else printf("Khong chia het cho so nao ca.");
    return 0;
}

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

Cách tiếp cận này sử dụng kiểu dữ liệu int cho cả ba biến n, a, b. Tuy nhiên, đề bài giới hạn giá trị lên tới 10^18, lớn hơn giới hạn của kiểu int (thường là 2^31-1 ≈ 2*10^9). Do đó, giải pháp này chỉ có thể chạy đúng với các test case nhỏ và sẽ bị overflow hoặc lỗi với input lớn.

Cách Sử dụng biến kiểu long long

#include <stdio.h>

int main(){
    long long n,a,b;
    scanf("%lld", &n);
    scanf("%lld %lld", &a, &b);
    if(n%a==0&&n%b==0) printf("Co, tat ca!");
    else if(n%a==0&&n%b!=0) printf("Chi chia het cho %lld,", a);
    else if(n%a!=0&&n%b==0) printf("Chi chia het cho %lld.", b);
    else printf("Khong chia het cho so nao ca.");
    return 0;
}

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

Đây là giải pháp tối ưu và chính xác. Sử dụng kiểu dữ liệu long long (64-bit integer) đảm bảo có thể lưu trữ số lớn lên tới 10^18. Toán tử modulo (%) được sử dụng để kiểm tra tính chia hết. Logic giải quyết bao gồm 4 trường hợp tương ứng với yêu cầu đề bài: chia hết cả hai, chỉ chia hết a, chỉ chia hết b, và không chia hết số nào.

Cách Sử dụng biến kiểu unsigned long long

#include <iostream>
using namespace std;

int main() {
    unsigned long long n, a, b;
    cin >> n >> a >> b;
    bool divA = (n % a == 0);
    bool divB = (n % b == 0);
    if (divA && divB) cout << "Co, tat ca!";
    else if (divA) cout << "Chi chia het cho " << a << ",";
    else if (divB) cout << "Chi chia het cho " << b << ".";
    else cout << "Khong chia het cho so nao ca.";
    return 0;
}

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

Giải pháp này sử dụng unsigned long long, cũng là kiểu 64-bit nhưng không có bit dấu, giúp giá trị dương lớn hơn một chút (lên tới 2^64-1). Về bản chất, logic tương tự như cách dùng long long, chỉ khác về kiểu dữ liệu. Việc lưu kết quả kiểm tra chia hết vào biến boolean (divA, divB) giúp code dễ đọc hơn nhưng không thay đổi độ phức tạp.

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

Bài học kinh nghiệm

• Độ lớn của input (10^18) yêu cầu phải sử dụng kiểu dữ liệu 64-bit (long long hoặc unsigned long long) thay vì int (32-bit).
• Bài toán chỉ cần sử dụng phép toán modulo (%) để kiểm tra chia hết, là thao tác cơ bản có độ phức tạp O(1) với số lớn.
• Cần tuân thủ chính xác định dạng xuất ra (dấu câu và dấu chấm) theo từng trường hợp.

Lỗi thường gặp

• Lỗi định dạng input/output: Sử dụng %d thay vì %lld sẽ gây lỗi khi đọc/ghi số lớn.
• Quên các trường hợp: Cần kiểm tra đủ 4 trường hợp (Cả hai, chỉ A, chỉ B, không cái nào) bằng if-else if-else để tránh trùng lặp kết quả.
• Vấn đề số âm: Dù đề bài nói số nguyên dương, nhưng nếu dùng int và số input lớn hơn giới hạn, nó có thể trở thành số âm do overflow, dẫn đến phép chia hết sai.