首页 > 代码库 > HDU 4389 数位dp

HDU 4389 数位dp

2024-09-09 21:19:43   215人阅读

X mod f(x)

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2992    Accepted Submission(s): 1171


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
21 1011 20
 

 

Sample Output
Case 1: 10Case 2: 3
 

 

Author
WHU
 

 

Source
2012 Multi-University Training Contest 9
 
 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 #include <stack> 7 #include <queue> 8 #include <cmath> 9 #include <map>10 #define ll  __int6411 #define dazhi 214748364712 #define bug() printf("!!!!!!!")13 #define M 10000514 using namespace  std;15 int bit[10];16 int dp[10][82][82][82];17 int  n;18 int  functi(int pos,int mod,int xx ,int sum,bool flag)19 {20     if(pos==0) return (xx==sum&&mod%sum==0);21     if(flag&&dp[pos][mod][xx][sum]!=-1) return dp[pos][mod][xx][sum];22     ll x=flag ? 9 : bit[pos];23     ll ans=0;24     for(ll i=0;i<=x;i++)25     ans+=functi(pos-1,(mod*10+i)%xx,xx,sum+i,flag||i<x);26     if(flag)27         dp[pos][mod][xx][sum]=ans;28     return ans;29 }30 int  fun(int x)31 {32     int len=0;33     while(x)34     {35         bit[++len]=x%10;36         x/=10;37     }38     ll re=0;39     for(int i=1;i<=81;i++)40         re+=functi(len,0,i,0,0);41     return re;42 }43 int main()44 {45    int t;46    int  l,r;47    while(scanf("%d",&t)!=EOF)48    {49        memset(dp,-1,sizeof(dp));50        for(int i=1;i<=t;i++)51        {52            scanf("%d %d",&l,&r);53            int exm=fun(r);54            printf("Case %d: %d\n",i,exm-fun(l-1));55        }56    }57     return 0;58 }

 

HDU 4389 数位dp


联系
我们