HDU 4722 Good Numbers(找规律+数位DP) - c++编程基础

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

Total Submission(s): 610 Accepted Submission(s): 225

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 <= 1018).

Output

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

Sample Input

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

第一种方法：

10-20 19 可以被10整除

20-30 28 可以被10整除

30-40 37 可以被10整除

律应该很显然了，0~10中有一个，10~20中有一个。。。一次的每十个中必有一个。可以自己在纸上画一下，、

import java.io.*;  
import java.util.*;  
public class Main {  
    BufferedReader bu;  
    PrintWriter pw;  
    long a;  
    long b,num1,num2;  
    int n;  
    public static void main(String[] args) throws IOException{  
        new Main().work();  
    }  
    void work() throws IOException{  
        bu=new BufferedReader(new InputStreamReader(System.in));  
        pw=new PrintWriter(new OutputStreamWriter(System.out),true);  
        n=Integer.parseInt(bu.readLine());  
        for(int p=1;p<=n;p++){  
            String str[]=bu.readLine().split(" ");  
            a=Long.parseLong(str[0]);  
            b=Long.parseLong(str[1]);  
              
            for(long i=a;;i++){  
                if(fun(i)){  
                    num1=i;//寻找可以被10整除的数  
                    break;  
                }  
            }  
            for(long i=b;;i--){  
                if(fun(i)){  
                    num2=i;//寻找可以被10整除的数  
                    break;  
                }  
            }  
            pw.print("Case #"+p+": ");  
            pw.println(num2/10-num1/10+1);  
        }  
    }  
    //判断每一位的和能否被10整除  
    boolean fun(long a){  
        long sum=0;  
        while(a!=0){  
            sum+=a%10;  
            a/=10;  
        }  
        if(sum%10==0)  
            return true;  
        return false;  
    }  
}

第二种方法

import java.io.*;  
import java.math.BigInteger;  
import java.util.*;  
public class Main {  
    int t;  
    long a,b;  
    PrintWriter pw;  
    long digdit[]=new long[30];  
    long[][] dp=new long[30][30];  
    public static void main(String[] args) throws IOException{  
        new Main().work();  
    }  
    void work() throws IOException{  
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));  
        pw=new PrintWriter(new OutputStreamWriter(System.out),true);  
        t=Integer.parseInt(bu.readLine());  
        for(int i=1;i<=t;i++){  
            pw.print("Case #"+i+": ");  
            String str[]=bu.readLine().split(" ");  
            a=Long.parseLong(str[0]);  
            b=Long.parseLong(str[1]);  
            long num1=dit(b);  
            long num2=dit(a-1);  
            long ans=num1-num2;  
            pw.println(ans);  
        }  
    }  
    long dit(long x){  
        int pos=0;  
        for(int i=0;i