Hướng dẫn cho Số ảo tưởng

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.

Tóm tắt đề bài

Cho một số nguyên dương \(n\). Một số \(x\) được gọi là số ảo tưởng nếu thỏa mãn đồng thời hai điều kiện:

Tổng các chữ số của \(x\) chia hết cho số lượng chữ số của \(x\).
Tích các chữ số của \(x\) chia hết cho tổng các chữ số của \(x\).

Yêu cầu: Đếm số lượng số ảo tưởng trong đoạn từ \(1\) đến \(n\).

Phân tích

Điều kiện: \(1 \leq n \leq 10^{12}\).
Với \(n\) lên đến \(10^{12}\), ta không thể duyệt từng số để kiểm tra. Đây là dấu hiệu của bài toán Quy hoạch động chữ số (Digit DP).
Gọi \(L\) là số lượng chữ số của \(x\), \(S\) là tổng các chữ số của \(x\), và \(P\) là tích các chữ số của \(x\).
- Điều kiện 1: \(S \pmod L = 0\).
- Điều kiện 2: \(P \pmod S = 0\).
Vì \(n \leq 10^{12}\), số lượng chữ số tối đa là \(12\). Tổng các chữ số tối đa là \(9 \times 12 = 108\).
Với mỗi độ dài \(L\) cố định, ta cần tìm các số có tổng chữ số \(S\) sao cho \(S\) là bội của \(L\) (\(S \in \{L, 2L, 3L, \dots\}\)). Với mỗi \(S\) như vậy, ta thực hiện Digit DP để đếm các số có tích các chữ số chia hết cho \(S\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt qua từng số từ \(1\) đến \(n\), viết hàm tính tổng chữ số, tích chữ số và kiểm tra các điều kiện đề bài.

Độ phức tạp

Thời gian: \(O(n \cdot \log_{10} n)\)
Đánh giá: Chỉ phù hợp với \(n \leq 10^6\). Với \(n = 10^{12}\), cách này sẽ chạy cực kỳ chậm.

Code Brute Force

C++

#include <bits/stdc++.h>
using namespace std;

bool check(long long x) {
    string s = to_string(x);
    int L = s.size();
    long long sum = 0, prod = 1;
    for (char c : s) {
        int d = c - '0';
        sum += d;
        prod *= d;
    }
    if (sum % L != 0) return false;
    if (sum == 0) return false; // Tránh chia cho 0
    return (prod % sum == 0);
}

int main() {
    long long n;
    cin >> n;
    int count = 0;
    for (long long i = 1; i <= n; i++) {
        if (check(i)) count++;
    }
    cout << count;
    return 0;
}

Python

def check(x):
    s = str(x)
    L = len(s)
    digits = [int(d) for d in s]
    sum_digits = sum(digits)
    prod_digits = 1
    for d in digits:
        prod_digits *= d

    if sum_digits % L != 0:
        return False
    if sum_digits == 0:
        return False
    return prod_digits % sum_digits == 0

n = int(input())
count = 0
for i in range(1, n + 1):
    if check(i):
        count += 1
print(count)

Hướng giải quyết (Tối ưu)

Ý tưởng chính

Sử dụng Quy hoạch động chữ số (Digit DP) kết hợp với việc cố định tổng chữ số \(S\).

Duyệt qua từng độ dài chữ số \(len\) từ \(1\) đến độ dài của \(n\).
Với mỗi độ dài \(len\), duyệt qua các giá trị tổng chữ số khả thi \(S\) sao cho \(S\) chia hết cho \(len\).
Với mỗi cặp \((len, S)\), ta dùng hàm dfs(pos, current_sum, current_prod_mod, tight) để đếm:
- pos: Vị trí chữ số đang xét.
- current_sum: Tổng các chữ số đã chọn.
- current_prod_mod: Tích các chữ số đã chọn lấy dư cho \(S\).
- tight: Biến nhớ để giới hạn chữ số không vượt quá số \(n\).
Lưu ý quan trọng:
- Khi tính tích dư cho \(S\), nếu \(S=0\) thì không hợp lệ. Nhưng theo đề bài \(x \geq 1\) nên \(S \geq 1\).
- Với các số có độ dài nhỏ hơn độ dài của \(n\), ta có thể coi như đang đếm các số nhỏ hơn hoặc bằng \(99\dots9\) (với \(len\) chữ số 9).
- Sử dụng memo (bảng phương án) để lưu trữ các trạng thái đã tính nhằm tối ưu thời gian.

Các bước thực hiện

Hàm solve(n): Chia bài toán thành hai phần:
- Đếm các số có số chữ số nhỏ hơn số chữ số của \(n\).
- Đếm các số có số chữ số bằng số chữ số của \(n\) và không vượt quá \(n\).
Trong mỗi phần, ta lặp qua các giá trị \(S = t \times len\) (với \(t \in [1, 9]\)) vì tổng chữ số tối đa của số có \(len\) chữ số là \(9 \times len\).

Độ phức tạp

Thời gian: \(O(D \times (9D) \times D \times (9D) \times 10)\), trong đó \(D\) là số chữ số (\(D \approx 12\)). Tổng số trạng thái DP cho mỗi \(S\) là khoảng \(12 \times 108 \times 108 \times 2\). Với số lượng \(S\) không quá lớn, thuật toán chạy tốt trong thời gian cho phép.
Bộ nhớ: \(O(D \times S \times S)\) để lưu bảng phương án.

Code tham khảo

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

string s;
map<tuple<int, int, int, bool>, ll> memo;

// pos: vị trí hiện tại, sum: tổng chữ số hiện tại, prod_mod: tích mod S, tight: giới hạn
ll dfs(int pos, int sum, int prod_mod, bool tight, int S, int len) {
    if (pos == len) {
        return (sum == S && prod_mod % S == 0);
    }

    auto key = make_tuple(pos, sum, prod_mod, tight);
    if (!tight && memo.count(key)) return memo[key];

    int limit = tight ? (s[pos] - '0') : 9;
    ll res = 0;

    for (int d = 0; d <= limit; d++) {
        // Không cho phép chữ số đầu tiên bằng 0 trừ khi số đó chỉ có 1 chữ số (nhưng đề bài x >= 1)
        if (pos == 0 && d == 0) continue;

        int new_sum = sum + d;
        if (new_sum > S) continue;

        int new_prod;
        // Nếu là chữ số đầu tiên, khởi tạo tích là d % S
        if (sum == 0) new_prod = d % S;
        else new_prod = (prod_mod * d) % S;

        res += dfs(pos + 1, new_sum, new_prod, tight && (d == limit), S, len);
    }

    if (!tight) memo[key] = res;
    return res;
}

ll solve(ll n) {
    string original_s = to_string(n);
    int N = original_s.size();
    ll ans = 0;

    // Xét các số có độ dài nhỏ hơn độ dài của n
    for (int len = 1; len < N; len++) {
        s = string(len, '9');
        for (int t = 1; t <= 9; t++) {
            int S = t * len;
            memo.clear();
            ans += dfs(0, 0, 1, true, S, len);
        }
    }

    // Xét các số có độ dài bằng độ dài của n
    s = original_s;
    for (int t = 1; t <= 9; t++) {
        int S = t * N;
        memo.clear();
        ans += dfs(0, 0, 1, true, S, N);
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;
    cout << solve(n);

    return 0;
}

Python

import sys

# Tăng giới hạn đệ quy cho DFS
sys.setrecursionlimit(2000)

def solve():
    line = sys.stdin.readline()
    if not line:
        return
    n_str = line.strip()
    n_val = int(n_str)

    memo = {}

    def dfs(pos, current_sum, prod_mod, tight, S, length, s_digits):
        if pos == length:
            return 1 if (current_sum == S and prod_mod % S == 0) else 0

        state = (pos, current_sum, prod_mod, tight)
        if not tight and state in memo:
            return memo[state]

        limit = s_digits[pos] if tight else 9
        res = 0

        for d in range(limit + 1):
            if pos == 0 and d == 0:
                continue

            new_sum = current_sum + d
            if new_sum > S:
                continue

            if current_sum == 0:
                new_prod = d % S
            else:
                new_prod = (prod_mod * d) % S

            res += dfs(pos + 1, new_sum, new_prod, tight and (d == limit), S, length, s_digits)

        if not tight:
            memo[state] = res
        return res

    ans = 0
    N = len(n_str)

    # Xét các số có độ dài nhỏ hơn N
    for length in range(1, N):
        s_digits = [9] * length
        for t in range(1, 10):
            S = t * length
            memo = {}
            ans += dfs(0, 0, 1, True, S, length, s_digits)

    # Xét các số có độ dài bằng N
    s_digits = [int(d) for d in n_str]
    for t in range(1, 10):
        S = t * N
        memo = {}
        ans += dfs(0, 0, 1, True, S, N, s_digits)

    print(ans)

solve()

Bình luận

Tải bình luận...

Không có bình luận nào.