LightOJ 1068数位dp - c++编程基础

Investigation

Time Limit: 2000MS

Memory Limit: 32768KB

64bit IO Format: %lld & %llu

[Submit] [Go Back] [Status]

Description

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

Sample Input

1 20 1

1 20 2

1 1000 4

Sample Output

Case 1: 20

Case 2: 5

Case 3: 64

Source

Problem Setter: Sohel Hafiz Special Thanks: Jane Alam Jan (Solution, Dataset)

求A到B之间满足可以整除K且各位加起来整除K的数的个数。

由于最大才2^31，当K>90时，答案显然为0，然后就是简单数位dp

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-7 16:17:23
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
                using namespace std; #define INF 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; int dp[15][110][110],num[15],K; int dfs(int pos,int st,int mod,bool flag){ if(pos==0)return mod==0&&st==0; if(flag&&dp[pos][st][mod]!=-1)return dp[pos][st][mod]; int ans=0,u=flag 9:num[pos]; for(int d=0;d<=u;d++) ans+=dfs(pos-1,(st*10+d)%K,(mod+d)%K,flag||d
                
                 >A>>B>>K; printf("Case %d: ",t); if(K>90)cout<<0<