Love no Exist

Investigation – LightOJ

  • No Comments

Đề bài

https://lightoj.com/problem/investigation

Tóm tắt

Tìm số lượng các số nguyên dương nằm trong khoảng [A, B] (1 ≤ A ≤ B ≤ 2^31) sao cho tổng các chữ số của chúng chia hết cho K. (1 ≤ K ≤ 10000)

Input

  • Dòng đầu tiên chứa số nguyên T (1 ≤ T ≤ 200), số lượng bộ test.
  • T dòng tiếp theo, mỗi dòng chứa 3 số nguyên A, B và K.

Output

  • Với mỗi bộ test, in ra số lượng các số thỏa mãn điều kiện.

Ví dụ

Input

C++
3
1 20 1
1 20 2
1 1000 4

Output

C++
Case 1: 20
Case 2: 5
Case 3: 64

Hướng dẫn giải

(Bữa nảo rảnh thì cập nhật sau)

Code

C++
#include <iostream>
#include <cstring>
using namespace std;

int t, a, b, k;
string nString;
int memo[10][2][90][90];

int dp(int index, bool tight, int sumMod, int sumDigitMod) {
    if (index == nString.size()) {
        if (sumMod == 0 && sumDigitMod == 0) {
            return 1;
        }

        return 0;
    }

    if (memo[index][tight][sumMod][sumDigitMod] != -1) {
        return memo[index][tight][sumMod][sumDigitMod];
    }

    int limit = (tight ? nString[index] - '0' : 9);
    int result = 0;
    for (int digit = 0; digit <= limit; ++digit) {
        bool newTight = tight && (digit == limit);
        int newSumMod = (sumMod * 10 + digit) % k;
        int newSumDigitMod = (sumDigitMod + digit) % k;
        result += dp(index + 1, newTight, newSumMod, newSumDigitMod);
    }

    memo[index][tight][sumMod][sumDigitMod] = result;
    return result;
}

int f(int n) {
    if (k > 90) {
        return 0;
    }
    nString = to_string(n);
    memset(memo, -1, sizeof(memo));
    return dp(0, true, 0, 0);
}

int main() {
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        cin >> a >> b >> k;
        cout << "Case " << i << ": " << f(b) - f(a - 1) << '\\n';
    }

    return 0;
}