hdu4933 Miaomiao's Function

水水的计数题，关键在细节。

 import java.math.BigInteger;

 import java.util.Scanner;

 import java.io.*;

 public class Main {

     BigInteger n0 = BigInteger.valueOf(0);

     BigInteger n1 = BigInteger.valueOf(1);

     BigInteger n2 = BigInteger.valueOf(2);

     BigInteger n10 = BigInteger.valueOf(10);

     BigInteger n9 = BigInteger.valueOf(9);

     BigInteger rev = BigInteger.valueOf(-1);

     BigInteger n45 = new BigInteger("45");

     BigInteger p[] = new BigInteger [110];

     BigInteger P[] = new BigInteger [110];

     BigInteger dP[] = new BigInteger [110];

     BigInteger M[] = new BigInteger [110];

     void init(){

         dP[0] = P[0] = p[0] = n0;

         M[0] = n1;

         for(int i = 1; i < 102; i++){

             //System.out.println(i);

             p[i] = M[i - 1].multiply(n45);

             p[i] = p[i].subtract(n9.multiply(P[i - 1]));

             //System.out.println(p[i]);

             //System.out.println("ok");

             P[i] = p[i].subtract(P[i - 1]);

             dP[i] = dP[i - 1].add(p[i]);

             M[i] = M[i - 1].multiply(n10);

             //System.out.println("M" + i + "  " + M[i]);

         }

     }

     BigInteger getAns(BigInteger num){

         if(num.equals(n0)) return n0;

         if(num.compareTo(n0) > 0 && num.compareTo(n9) <= 0) return num.add(n1).multiply(num).divide(n2);

         String str = num.toString();

         int len = str.length();

         BigInteger first = num.divide(M[len - 1]);

         BigInteger new_num = num.mod(M[len - 1]);

         BigInteger tem = dP[len - 1];

         //System.out.println("tem" + tem);

         tem = tem.add(M[len - 1].multiply(first.multiply(first.subtract(n1)).divide(n2)));

         tem = tem.subtract((first.subtract(n1)).multiply(P[len - 1]));

         tem = tem.add(new_num.add(n1).multiply(first));

         if(new_num.equals(n0)) return tem;

         BigInteger sign = n1;

         int tmp = len - 1;

         while(new_num.divide(M[tmp]).equals(n0)){

              tmp--;

              sign = sign.multiply(rev);

         }

         while(new_num.compareTo(n0) > 0){

             //System.out.println("tem " + tem);

             //System.out.println("new_num" + new_num);

             String new_str = new_num.toString();

             int new_len = new_str.length();

             BigInteger new_sign = (len - 1) % 2 == 0 ? n1 : rev;

             int i = 1;

             //System.out.println("new_len" + new_len);

             while(i < new_len){

                 tem = tem.add(new_sign.multiply(p[i]));

                 //System.out.println("i" + i + "p[i]" + p[i] + "tem" + tem);

                 new_sign = new_sign.multiply(rev);

                 i++;

             }

             //System.out.println("ok");

             //System.out.println("new_sign" + new_sign);

             BigInteger new_first = new_num.divide(M[new_len - 1]);

             tem = tem.add(new_first.subtract(n1).multiply(new_first).divide(n2).multiply(M[new_len - 1]).multiply(new_sign));

             //System.out.println("tem" + tem);

             tem = tem.add(new_sign.multiply(rev).multiply(new_first.subtract(n1)).multiply(P[new_len - 1]));

             //System.out.println("tem" + tem);

             new_num = new_num.mod(M[new_len - 1]);

             tem = tem.add(new_first.multiply(n1.add(new_num)).multiply(new_sign));

         }

         return tem;

     }

     BigInteger f(BigInteger num){

         if(num.compareTo(n0) < 0){

             BigInteger tem = num.divide(n9);

             num = num.add(tem.multiply(n9).multiply(rev));

             while(num.compareTo(n0) > 0) num = num.subtract(n9);

             while(num.compareTo(n0) <= 0) num = num.add(n9);

         }

         if(num.compareTo(n0) >= 0 && num.compareTo(n9) <= 0) return num;

         BigInteger tem = n0;

         while(num.compareTo(n0) > 0){

             tem = tem.add(num.mod(n10));

             num = num.divide(n10);

         }

         return f(tem);

     }

     void solve(){

         Scanner cin = new Scanner(System.in);

         int T = cin.nextInt();

         while(T-- != 0){

             String stra = cin.next();

             String strb = cin.next();

             BigInteger a = new BigInteger(stra);

             BigInteger b = new BigInteger(strb);

             BigInteger front = a.equals(n0) ? n0 : getAns(a.subtract(n1));

             BigInteger rear = getAns(b);

             //System.out.println("rear" + rear);

             BigInteger ans = rear.subtract(front);

             BigInteger fAns = f(ans);

             if(fAns.equals(n0)) System.out.println("Error!");

             else{

                 // System.out.println("ans" + ans);

                 //System.out.println("fAns" + fAns);

                 ans = ans.mod(fAns).add(fAns).mod(fAns);

                 System.out.println(ans);

             }

         }

         cin.close();

     }

     public static void main(String[] args) throws IOException{

         Main e = new Main();

         e.init();

         e.solve();

     }

 }