Editorial for ptit005: Số đặc biệt

Hiểu bài toán

Một số n được gọi là 'số đặc biệt' nếu nó chia hết cho tổng các chữ số của chính nó. Bài toán yêu cầu kiểm tra xem một số n (1 ≤ n ≤ 10^18) cho trước có phải là số đặc biệt hay không. Nếu có, in ra 'YES', ngược lại in ra 'NO'.

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

Cách Giải pháp trực quan (Tính tổng chữ số)

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

void tachso(ll n){
    ll c = n;
    ll sum = 0;
    while(c){
        sum += c % 10;
        c /= 10;
    }
    if(n % sum == 0) printf("YES");
    else printf("NO");
}

int main(){
    ll n;
    scanf("%lld",&n);
    tachso(n);
    return 0;
}

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

Đây là cách tiếp cận đơn giản nhất để giải quyết bài toán. Thuật toán thực hiện các bước sau:

1. Đọc vào số n (sử dụng kiểu dữ liệu long long).
2. Khởi tạo biến tổng (sum) bằng 0.
3. Dùng vòng lặp while để lặp qua từng chữ số của n:
   • Lấy chữ số cuối cùng bằng phép chia lấy dư cho 10 (n % 10).
   • Cộng chữ số đó vào biến tổng.
   • Loại bỏ chữ số cuối cùng bằng phép chia nguyên cho 10 (n /= 10).
4. Sau khi tính được tổng các chữ số (tạm gọi là S), kiểm tra điều kiện n có chia hết cho S hay không (n % S == 0).
5. In kết quả 'YES' hoặc 'NO' tương ứng. Vì số n có tối đa 18 chữ số, độ phức tạp của thuật toán này là O(log n) (tương đương O(18)), rất nhanh và hiệu quả.

Cách Hàm trả về giá trị boolean

#include<stdio.h>
typedef long long ll;
ll tongchuso(ll n){
    ll tong = 0;
    while(n > 0){
        tong += n % 10;
        n /= 10;
    }
    return tong;
}
ll lasodacbiet(ll n){
    ll tong = tongchuso(n);
    return (n % tong == 0);
}
int main(){
    ll n;
    scanf("%lld",&n);
    if(lasodacbiet(n)){
        printf("YES\n");
    }else{
        printf("NO\n");
    }
}

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

Cách tiếp cận này có logic tương tự như cách đầu tiên, nhưng được tổ chức code theo hướng module hóa hơn.

1. Hàm tongchuso(n): Nhận vào một số n và trả về tổng các chữ số của nó.
2. Hàm lasodacbiet(n): Gọi hàm tongchuso để lấy tổng chữ số, sau đó kiểm tra n có chia hết cho tổng này không. Hàm trả về 1 (true) nếu là số đặc biệt, 0 (false) nếu không.
3. Hàm main: Đọc dữ liệu, gọi hàm kiểm tra và in kết quả. Phương pháp này giúp code dễ đọc và dễ bảo trì hơn, đặc biệt là khi logic kiểm tra có thể được sử dụng lại ở nhiều nơi. Độ phức tạp vẫn giữ nguyên O(log n).

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

Bài học kinh nghiệm

• Bài toán chỉ yêu cầu kiểm tra tính chia hết, nên ta chỉ cần tập trung vào phép tính tổng các chữ số.
• Với giới hạn n ≤ 10^18, số lượng chữ số rất nhỏ (tối đa 18), nên thuật toán lặp qua từng chữ số là hoàn toàn đủ nhanh (O(log n)).
• Phải sử dụng kiểu dữ liệu long long (hoặc unsigned long long) để lưu trữ giá trị n, tránh tràn số với các biến kiểu int.

Lỗi thường gặp

• Sử dụng kiểu int để lưu n: Với n lên tới 10^18, int (thường là 32-bit) sẽ tràn số, dẫn đến lỗi tính toán.
• Chia cho 0: Nếu n là bội của 10 (ví dụ: 10, 20, 100...), tổng các chữ số của n có thể là 10, 2, 1... đều khác 0. Tuy nhiên, nếu n=0 (mặc dù đề bài n ≥ 1), tổng chữ số là 0 sẽ gây lỗi chia cho 0. Trong bài này n ≥ 1 nên không gặp lỗi này, nhưng cần lưu ý trong các bài toán tổng quát hơn.