2015
05-24

# hdu 4389-x mod f(x)-动态规划-[解题报告]hoj

Problem Description
Here is a function f(x):
int f ( int x ) {
if ( x == 0 ) return 0;
return f ( x / 10 ) + x % 10;
}


Now, you want to know, in a given interval [A, B] (1 <= A <= B <= 109), how many integer x that mod f(x) equal to 0.

Input
The first line has an integer T (1 <= T <= 50), indicate the number of test cases.
Each test case has two integers A, B.

Output
For each test case, output only one line containing the case number and an integer indicated the number of x.

Sample Input
2
1 10
11 20

Sample Output
Case 1: 10
Case 2: 3

d[l][i][j][k]表示前l位和为i模j的结果为k的数的个数，那么就有方程

d[l+1][i+x][j][(k*10+x)%j] += d[l][i][j][k]

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int bit[10];
int dp[10][82][82][82];
//d[l][i][j][k]表示前l位和为i模j的结果为k的数的个数
void set()
{
int i,j,k,l,x;
for(i = 1; i<=81; i++)
dp[0][0][i][0] = 1;
for(l = 0; l<9; l++)
for(i = 0; i<=l*9; i++)
for(j = 1; j<=81; j++)
for(k = 0; k<j; k++)
for(x = 0; x<=9; x++)
dp[l+1][i+x][j][(k*10+x)%j] += dp[l][i][j][k];
}

int solve(int n)
{
if(!n)
return 0;
int ans,i,j,k,len;
int sum,tem1,tem2,s,bit[10],r;
len = sum = ans = 0;
tem1 = tem2 = n;
s = 1;
while(tem1)
{
bit[++len] = tem1%10;
tem1/=10;
sum+=bit[len];//每位数之和
}
if(n%sum==0)//本身要先看是否整除
ans++;
for(i = 1; i<=len; i++)
{
sum-=bit[i];//将该位清0
tem2/=10;
s*=10;
tem1 = tem2*s;
for(j = 0; j<bit[i]; j++) //枚举该位的状况
{
for(k = sum+j; k<=sum+j+9*(i-1); k++) //该位与更高位的和，而比该位低的和择优9*(i-1)种
{
if(!k)//和为0的状况不符合
continue;
r = tem1%k;//现在该数对各位和进行取余
if(r)
r = k-r;//余数大于0，那么k-dd得到的数肯定能被t整除
ans+=dp[i-1][k-sum-j][k][r];//加上个数
}
tem1+=s/10;//标记现在算到哪里，例如1234，一开始t是1230，然后1231,1232,1233,1234，接下来1200，就是1210，1220,1230
}
}
return ans;
}

int main()
{
int T,l,r,cas = 1;
set();
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&l,&r);
printf("Case %d: %d\n",cas++,solve(r)-solve(l-1));
}

return 0;
}