Đếm số thỏa mãn m + sum(m) + sum(sum(m)) = N trong C++

Cho số N đầu vào. Mục tiêu: tìm các số m đến N thỏa mãn điều kiện sau (N <= 10^9):

m + sum(m) + sum(sum(m)) = N. Trong đó sum(m) là tổng các chữ số của m.

Ví dụ: m = 137 → sum(m) = 1+3+7=11, sum(sum(m)) = sum(11) = 1+1=2.

Hiểu qua ví dụ

Đầu vào: N = 27

Đầu ra: Số lượng số thỏa mãn: 3

Giải thích: Các số:

• 9 (9 + 9 + 9 = 27)
• 15 (15 + (1+5) + 6 = 27)
• 21 (21 + (2+1) + 3 = 27)

Đầu vào: N = 81

Đầu ra: Số lượng số thỏa mãn: 2

Giải thích: Các số:

• 63 (63 + (6+3) + 9 = 81)
• 66 (66 + (6+6) + (1+2) = 81)

Phương pháp sử dụng

Tính tổng chữ số của các số và so sánh tổng cộng với N. Nếu bằng N tăng đếm.

Số lớn nhất có thể là 10^9 → tổng chữ số tối đa của m là 81 (9*9), tổng chữ số tiếp theo của sum(sum(m)) tối đa 16 (7+9 cho 79). Do đó chỉ cần kiểm tra từ N-97 đến N vì các số nhỏ hơn N-97 và lớn hơn N không thỏa mãn.

• Nhập số nguyên N.
• Hàm total(int num) trả về tổng chữ số của num.
• Khởi tạo res_total = 0, res = 0.
• Vòng lặp while lấy chữ số đơn vị: res = num % 10, cộng vào res_total, num = num / 10.
• Trả về res_total.
• Hàm condition(int N) trả về số lượng số thỏa mãn.
• Khởi tạo count = 0.
• Vòng lặp for từ i = N - 97 đến i <= N.
• Tính temp_1 = total(i), temp_2 = total(temp_1).
• temp_3 = i + temp_1 + temp_2. Nếu bằng N tăng count.
• Trả về count.

Ví dụ mã nguồn

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

int total(int num) { 
    int res_total = 0; 
    int res = 0; 
    while (num > 0) { 
        res = num % 10; 
        res_total = res_total + res; 
        num = num / 10; 
    } 
    return res_total; 
} 

int condition(int N) { 
    int count = 0; 
    for (int i = N - 97; i <= N; i++) { 
        int temp_1 = total(i); 
        int temp_2 = total(temp_1); 
        int temp_3 = i + temp_1 + temp_2; 
        if (temp_3 == N) count++; 
    } 
    return count; 
} 

int main() { 
    int N = 9999; 
    cout << "Count of numbers satisfying m + sum(m) + sum(sum(m)) = N are: " << condition(N); 
    return 0; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of numbers satisfying m + sum(m) + sum(sum(m)) = N are: 2