HDU4722-Good Numbers

Good Numbers

                                                                               Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

                                                                                                          Total Submission(s): 4871    Accepted Submission(s): 1545

Problem Description If we sum up every digit of a number and the result can be exactly divided by 10, we say this number is a good number.

You are required to count the number of good numbers in the range from A to B, inclusive.  

Input The first line has a number T (T <= 10000) , indicating the number of test cases.

Each test case comes with a single line with two numbers A and B (0 <= A <= B <= 10 18).  

Output For test case X, output "Case #X: " first, then output the number of good numbers in a single line.  

Sample Input

2
1 10
1 20
        

Sample Output

Case #1: 0
Case #2: 1

   
    
     Hint
    
The answer maybe very large, we recommend you to use long long instead of int.

   
    
        

Source 2013 ACM/ICPC Asia Regional Online —— Warmup2  

Recommend zhuyuanchen520  

题意：找Good Numbers一个数N，如果它每一个位数字之和可以整除10，那么它就是Good Numbers，比如451就是一个4 + 5 + 1 = 10，求[A, B]之间这样的数的个数

解题思路：数位dp或找规律，找规律是先写个暴力找规律，可以发现0~n-1的good number个数是n/10+（从n/10*10 枚举到n的个数）

找规律

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <climits>

using namespace std;

#define LL long long
const int INF=0x3f3f3f3f;

int main()
{
    int t,cas=0;
    scanf("%d",&t);
    while(t--)
    {
        LL ans1=0,ans2=0,sum1=0,sum2=0;
        LL a,b;
        scanf("%lld%lld",&a,&b);
        a--;
        if(a>=9)
        {
            ans1+=a/10;
            LL aa=a%10;
            a/=10;
            while(a)
            {
                sum1+=a%10;
                a/=10;
                sum1%=10;
            }
            for(LL i=0;i<=aa;i++)
                if((sum1+i)%10==0) ans1++;
        }
        else if(a==-1) ans1=0;
        else ans1=1;
        if(b>=10)
        {
            ans2+=b/10;
            LL bb=b%10;
            b/=10;
            while(b)
            {
                sum2+=b%10;
                b/=10;
                sum2%=10;
            }
            for(LL i=0;i<=bb;i++)
                if((sum2+i)%10==0) ans2++;
        }
        else ans2=1;
        printf("Case #%d: %lld\n",++cas,ans2-ans1);
    }
    return 0;
}
           

数位dp

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <climits>
#include <functional>

using namespace std;

#define LL long long
const int INF=0x3f3f3f3f;
const double exps=1e-8;

LL b[20];
LL dp[20][10];

LL solve(LL n)
{
    LL len=0,x=0;
    memset(dp,0,sizeof dp);
    while(n)
    {
        b[++len]=n%10;
        n/=10;
    }
    for(int i=1;i<=len/2;i++)
    {
        LL k=b[i];
        b[i]=b[len-i+1];
        b[len-i+1]=k;
    }
    x=0;
    for(int i=1;i<=len;i++)
    {
        for(int j=0;j<10;j++)
            for(int k=0;k<10;k++)
                dp[i][(j+k)%10]+=dp[i-1][j];
        for(int j=0;j<b[i];j++)
            dp[i][(x+j)%10]++;
        x=(x+b[i])%10;
    }
    if(!x) dp[len][0]++;
    return dp[len][0];
}

int main()
{
    LL t,l,r,cas=1;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%I64d%I64d",&l,&r);
        printf("Case #%lld: %lld\n",cas++,solve(r)-solve(l-1));
    }
    return 0;
}