Đếm số trong khoảng chia hết cho m và có chữ số d ở vị trí chẵn trong C++

Cho một khoảng nguyên, biến m làm ước số và biến d để kiểm tra chữ số d có ở vị trí chẵn hay không. Nhiệm vụ: đếm các số trong khoảng chia hết cho m và có chữ số d ở vị trí chẵn.

Ví dụ

Đầu vào: start = 20, end = 50, d = 8, m = 4

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

Giải thích: Khoảng 20-50. Các số có chữ số 8 ở vị trí chẵn: 28, 38, 48. Trong đó 24 và 48 chia hết cho 4 → đếm = 2.

Đầu vào: start = 10, end = 100, d = 6, m = 2

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

Giải thích: Các số có 6 ở vị trí chẵn: 16, 26, 36, 46, 56, 66, 76, 86, 96 (loại 6 và 66 vì ở vị trí lẻ). Tất cả đều chia hết cho 2 → đếm = 8.

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

• Tạo dải số từ start đến end, khai báo d, m truyền cho hàm.
• Tạo vector vec lưu chữ số (tách bằng %10, /10, sau đó reverse).
• Khởi tạo mảng arr với -1 bằng memset.
• Gọi set_total(0, 0, 0, vec) kiểm tra số có vị trí chẵn là d và chia hết cho m.
• Trong set_total:
  • Nếu place == vec.size() kiểm tra temp == 0 trả về 1 else 0.
  • Nếu arr[place][temp][val] != -1 trả về giá trị đã lưu.
  • Nếu vị trí lẻ (place % 2 == 1): kiểm tra d so với vec[place], đệ quy với tổng modulo m.
  • Nếu vị trí chẵn: duyệt 0-9, bỏ qua i == d, đệ quy tính số cách.

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 
int arr[20][20][2]; 
int d, m; 

int set_total(int place, int temp, int val, vector<int> vec) { 
    if (place == vec.size()) { 
        if (temp == 0) return 1; 
        return 0; 
    } 
    if (arr[place][temp][val] != -1) { 
        return arr[place][temp][val]; 
    } 
    if (place % 2) { 
        if (val == 0) { 
            if (d > vec[place]) return 0; 
        } 
        int temp_2 = val; 
        if (d < vec[place]) temp_2 = 1; 
        int temp_3 = set_total(place + 1, (10 * temp + d) % m, temp_2, vec); 
        return arr[place][temp][val] = temp_3; 
    } 
    int count = 0; 
    int set_limit = (val ? 9 : vec[place]); 
    for (int i = 0; i <= set_limit; i++) { 
        if (i == d) continue; 
        int temp_2 = val; 
        if (i < vec[place]) temp_2 = 1; 
        count += set_total(place + 1, (10 * temp + i) % m, temp_2, vec); 
    } 
    return arr[place][temp][val] = count; 
} 

int divisible(int val) { 
    vector<int> vec; 
    while (val) { 
        vec.push_back(val % 10); 
        val = val / 10; 
    } 
    reverse(vec.begin(), vec.end()); 
    memset(arr, -1, sizeof(arr)); 
    return set_total(0, 0, 0, vec); 
} 

int main() { 
    int start = 20, end = 50; 
    d = 8, m = 4; 
    int count = divisible(end) - divisible(start); 
    cout << "Count of Numbers in a Range divisible by m and having digit d in even positions are: " << count; 
    return 0; 
}

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

Kết quả

Count of Numbers in a Range divisible by m and having digit d in even positions are: 2