数位DP
f[位数][自身模k余数][各位数字之和模k余数][当前位是否有上限]=方案数
k<10000，空间不够，如何优化？
不必优化，2^31以内，数字最多只有10位，各位数字之和最多为99(10个9)，所以k>99时肯定无解。数组开到100+就可以了
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=100010; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 14 return x*f; 15 } 16 int f[13][110][110]; 17 int x[13],cnt=0; 18 int a,b,k; 19 inline void dv(int t){ 20 cnt=0; 21 while(t){x[++cnt]=t%10;t/=10;} 22 memset(f,-1,sizeof f); 23 return; 24 } 25 int DP(int p,int m1,int m2,bool flag){ 26 if(flag && f[p][m1][m2]>=0)return f[p][m1][m2]; 27 if(!p)return (!m1 && !m2); 28 int lim=flag?9:x[p]; 29 int res=0; 30 for(int i=0;i<=lim;i++) 31 res+=DP(p-1,(m1*10+i)%k,(m2+i)%k,flag||(i<lim)); 32 if(flag)f[p][m1][m2]=res; 33 return res; 34 } 35 int main(){ 36 int i,j; 37 int T=read(); 38 while(T--){ 39 scanf("%d%d%d",&a,&b,&k); 40 if(k>100){printf("0 ");continue;} 41 dv(b); 42 int ans=DP(cnt,0,0,0); 43 dv(a-1); 44 ans-=DP(cnt,0,0,0); 45 printf("%d ",ans); 46 } 47 return 0; 48 }