| Time Limit: 2000MS | Memory Limit: 32768KB | 64bit IO Format: %lld & %llu |
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 < 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 byK.
Sample Input
3
1 20 1
1 20 2
1 1000 4
Sample Output
Case 1: 20
Case 2: 5
Case 3: 64
Source
求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 <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
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<u);
if(flag)dp[pos][st][mod]=ans;
return ans;
}
int solve(int x){
memset(dp,-1,sizeof(dp));
int len=0;
while(x){
num[++len]=x%10;
x/=10;
}
return dfs(len,0,0,0);
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int T,A,B,t;
scanf("%d",&T);
for(t=1;t<=T;t++){
cin>>A>>B>>K;
printf("Case %d: ",t);
if(K>90)cout<<0<<endl;
else cout<<solve(B)-solve(A-1)<<endl;
}
return 0;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/18965379