Uva_11361 Investigating Div-Sum Property

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 #define LL long long 
 7 #define MAXN 11
 8 int num[MAXN];
 9 int e[MAXN];
10 LL f[MAXN][100][100];
11 int A, B, K, len;
12 void init()
13 {
14     e[0] = 1;
15     for(int i = 1; i < MAXN; i ++)
16         e[i] = e[i-1] * 10;
17 }
18 LL func(int x)
19 {
20     //
21     memset(num, 0, sizeof(num));
22     memset(f, 0, sizeof(f));
23     int s1 = 0;
24     int s2 = 0;
25     for(int i = 10; i >=0; i --)
26     {
27         num[i] = x % 10;
28         x /= 10;
29     }
30     for(int  i = 0; i < 10; i ++)
31     {
32         s1 = (s1 + num[i]) % K;
33         s2 = (s2 * 10 + num[i]) % K;
34         for(int s_mod = 0; s_mod < K; s_mod ++)
35             for(int x_mod = 0; x_mod < K; x_mod ++)
36                 for(int p = 0; p < 10; p ++)
37                     f[i + 1][(s_mod + p) % K][(x_mod * 10 + p) % K] += f[i][s_mod][x_mod];
38         for(int j = 0; j < num[i + 1]; j ++)
39             f[i + 1][(s1 + j) % K][(s2 * 10 + j) % K] ++;
40     }
41     if((s1 + num[10]) % K == 0 && (s2 * 10 + num[10]) % K == 0) ++ f[10][0][0];
42     return f[10][0][0];
43 }
44 
45 int main()
46 {
47     init();
48     int T;
49     scanf("%d",&T);
50     while(T--)
51     {
52         scanf("%d %d %d",&A, &B, &K);
53         if(K >= 83)
54             printf("0\n");
55         else 
56             printf("%lld\n", func(B) - func(A - 1));
57     }
58     return 0;
59 }