先上代码 以后再说
#include <cstdio>
#include <cstring>
const int maxn = 110;
int dp[maxn][maxn][maxn];
int ok(int x, int k)
{
if(x < 10)
return x / k;
int a = x;
int b = 1;
int l = 0;
while(a)
{
l++;
a /= 10;
b *= 10;
}
b /= 10;
//printf("%d %d\n", a, b);
int ret = 0;
int m1 = 0, m2 = 0;
int d = 1;
while(l--)
{
int c = x / b;
//printf("%d\n", c);
if(l == 0)
{
for(int j = 0; j <= c; j++)
if(((k-j-m1)%k+k)%k == 0 && ((k-j-m2)%k+k)%k == 0)
ret++;
break;
}
for(int j = 0; j < c; j++)
ret += dp[l-1][((k-j-m1)%k+k)%k][((k-j*b-m2)%k+k)%k];
// printf("%d\n", c);
m1 += c;
m2 += c*b;
x -= c*b;
b /= 10;
}
return ret-1;
}
int main()
{
int T;
int a, b, k;
scanf("%d", &T);
while(T--)
{
scanf("%d %d %d", &a, &b, &k);
if(k > 82)
{
printf("0\n");
continue;
}
int c = a, d = 1;
memset(dp, 0, sizeof(dp));
for(int i = 0; i < 10; i++)
dp[0][i%k][i%k]++;
for(int i = 1; i <= 10; i++)
{
d *= 10;
if(d * 10 > b)
{
//printf("%d\n", d);
break;
}
for(int m1 = 0; m1 < k; m1++)
{
for(int m2 = 0; m2 < k; m2++)
{
for(int j = 0; j < 10; j++)
{
dp[i][((m1+j)%k+k)%k][((m2+j*d)%k+k)%k] += dp[i-1][m1][m2];
}
}
}
}
printf("%d\n", ok(b,k)-ok(a-1,k));
}
return 0;
}