Hiểu bài toán

Cho một số tự nhiên n (n < 1000000). Xét dãy số các số có dạng 3, 33, 333, ..., nghĩa là số chỉ chứa chữ số 3. Yêu cầu tìm số lượng chữ số 3 của số đầu tiên trong dãy số này chia hết cho n. Nếu không t tồn tại số nào chia hết cho n, in ra -1.

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

Cách Brute Force

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n;
    cin >> n;
    long long rem = 0;
    for (long long i = 1; i <= n; i++) {
        rem = (rem * 10 + 3) % n;
        if (rem == 0) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

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

Approach này sử dụng phương pháp lặp để mô phỏng phép chia. Thay vì xây dựng số hoàn chỉnh (có thể rất lớn), ta chỉ quan tâm đến số dư của phép chia. Gọi Rk là số dư của số có k chữ số 3 khi chia cho n. Ta có thể tính Rk theo công thức truy hồi: Rk = (R{k-1} * 10 + 3) % n. Ta bắt đầu với R0 = 0 và lặp cho đến khi tìm được Rk = 0. Nếu duyệt qua k từ 1 đến n mà không tìm thấy, thuật toán dừng lại và trả về -1.

Cách Optimized Loop

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int rem = 0;
    for (int k = 1; k <= n+5; k++) {
        rem = (rem * 10 + 3) % n;
        if (rem == 0) {
            cout << k << "\n";
            return 0;
        }
    }
    cout << -1 << "\n";
    return 0;
}

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

Đây là phiên bản tối ưu hóa của Brute Force. Thay vì chỉ kiểm tra điều kiện chia hết cho 2 và 5, giải pháp này dựa trên nguyên lý Dirichlet để đảm bảo tìm được kết quả trong vòng lặp. Tuy nhiên, giải pháp này có thể chạy nhiều hơn mức cần thiết nếu n không có nghiệm. Việc thêm ios::sync_with_stdio(false); và cin.tie(nullptr); giúp tăng tốc độ nhập xuất. Vòng lặp chạy tối đa n + 5 lần thay vì n.

Cách Mathematical Optimization

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n;
    cin >> n;
    if (n % 2 == 0 || n % 5 == 0) {
        cout << -1;
        return 0;
    }
    long long rem = 0;
    for (long long i = 1; i <= n; i++) {
        rem = (rem * 10 + 3) % n;
        if (rem == 0) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

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

Giải pháp này kết hợp một kiểm tra toán học quan trọng trước khi chạy vòng lặp. Nếu n chia hết cho 2 hoặc 5 (nghĩa là n chứa các thừa số nguyên tố 2 hoặc 5), thì không có số nào trong dãy 3, 33, 333... chia hết cho n. Điều này là vì các số này không chia hết cho 2 hay 5. Nếu kiểm tra này thất bại, thuật toán thực hiện vòng lặp mô phỏng phép chia tương tự như Brute Force. Đây là giải pháp tối ưu nhất về mặt hiệu năng thực tế.

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

Bài học kinh nghiệm

• Số 3, 33, 333... là các số có dạng 'Tứ giác' (Repunits) nhân với 3. Vấn đề có nghiệm thực sự khi và chỉ khi n không chứa thừa số nguyên tố 2 hoặc 5.
• Thay vì lưu trữ số thực tế (có thể có hàng triệu chữ số), ta chỉ cần duy trì số dư của phép chia (remainder) để kiểm tra tính chia hết.

Lỗi thường gặp

• Sử dụng các kiểu dữ liệu số nguyên quá nhỏ (như int) cho số dư có thể gây tràn số (overflow) nếu n rất lớn và phép nhân 10 được thực hiện trước khi chia lấy dư.
• Nếu không kiểm tra điều kiện n chia hết cho 2 hoặc 5, vòng lặp có thể chạy không giới hạn hoặc quá lâu đối với các input như 2, 5, 10, v.v., mặc dù logic vòng lặp i <= n sẽ ngăn lỗi vô hạn.