An integer is divisible by 3 if the sum of its digits is also divisible by 3. For example, 3702 is divisible by 3 and 12 (3+7+0+2) is also divisible by 3. This property also holds for the integer 9.

In this problem, we will investigate this property for other integers.

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case contains three positive integers A, B and K (1 ≤ A ≤ B < 2³¹ and 0 < K < 10000).

Output

For each case, output the case number and the number of integers in the range [A, B] which are divisible by K and the sum of its digits is also divisible by K.

题意：给你3个数A，B，K，求A～B之间有几个数能被K整除，而且各位数之和也能被K整除。

这题类似hdu3652，方法类似，就是k看起来有点大有10000这么大，但是这么大并没什么用啊，总共不超过10位位数之和最多才90。

所以当k大于90时，直接是0了。

dp[len][mod][count]，len表示当前位数，mod表示上一位数 mod k 的余数，count表示位数之和。

#include <iostream>

#include <cstring>

using namespace std;

typedef long long ll;

ll dp[20][100][100];

ll a[20] , b[20];

int k;

ll dfs(int len , int mod , int flag , ll s[] , int count) {

    if(len == 0) {

        return mod == 0 && (count % k) == 0;

    }

    if(!flag && dp[len][mod][count] != -1) {

        return dp[len][mod][count];

    }

    int t = flag ? s[len] : 9;

    ll sum = 0;

    for(int i = 0 ; i <= t ; i++) {

        sum += dfs(len - 1 , (mod * 10 + i) % k , flag && i == t , s , count + i);

    }

    if(!flag)

        dp[len][mod][count] = sum;

    return sum;

}

ll Get(int x , int y) {

    int len1 = 0 , len2 = 0;

    memset(dp , -1 , sizeof(dp));

    memset(a , 0 , sizeof(a));

    memset(b , 0 , sizeof(b));

    while(x) {

        a[++len1] = x % 10;

        x /= 10;

    }

    while(y) {

        b[++len2] = y % 10;

        y /= 10;

    }

    return dfs(len1 , 0 , 1 , a , 0) - dfs(len2 , 0 , 1 , b , 0);

}

int main()

{

    int t;

    cin >> t;

    int ans = 0;

    while(t--) {

        ans++;

        int A , B;

        cin >> A >> B >> k;

        cout << "Case " << ans << ": ";

        if(k >= 90)

            cout << 0 << endl;

        else

            cout << Get(B , A - 1) << endl;

    }

    return 0;

}

巴特西

lightoj 1068 - Investigation(数位dp）

Input

Output

最新文章

热门文章