Investigation （数位dp）

Investigation （数位dp）

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 < 231 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.

Sample Input

3

1 20 1

1 20 2

1 1000 4

Sample Output

Case 1: 20

Case 2: 5

Case 3: 64

题目大概：

求在两个数n和m之间能够整除k，并且所有位数之和也能整除k的数的数量。

思路：

基本数位dp，拿出两个状态，这个数字和每位数来讨论就可以了。

代码：

#include #include #include using namespace std;int a[20];int dp[20][100][100][2];int sove(int pos,int ge,int sum,int k,int limit){ if(pos==-1)return !ge&&!sum; if(!limit&&dp[pos][ge][sum][limit]!=-1)return dp[pos][ge][sum][limit]; int ans=0; int end=limit?a[pos]:9; for(int i=0;i<=end;i++) { ans+=sove(pos-1,(ge+i)%k,(sum*10+i)%k,k,limit&&(i==a[pos])); } if(!limit)dp[pos][ge][sum][limit]=ans; return ans;}int go(int x,int k){ int pos=0; while(x) { a[pos++]=x%10; x/=10; } return sove(pos-1,0,0,k,1);}int main(){ int t; int n,m,k; int ans; scanf("%d",&t); for(int i=1;i<=t;i++) { memset(dp,-1,sizeof(dp)); scanf("%d%d%d",&n,&m,&k); if(k>=95)ans=0; else ans=go(m,k)-go(n-1,k); printf("Case %d: %d\n",i,ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。