水水的计数题，关键在细节。
1 import java.math.BigInteger; 2 import java.util.Scanner; 3 import java.io.*; 4 5 public class Main { 6 BigInteger n0 = BigInteger.valueOf(0); 7 BigInteger n1 = BigInteger.valueOf(1); 8 BigInteger n2 = BigInteger.valueOf(2); 9 BigInteger n10 = BigInteger.valueOf(10); 10 BigInteger n9 = BigInteger.valueOf(9); 11 BigInteger rev = BigInteger.valueOf(-1); 12 BigInteger n45 = new BigInteger("45"); 13 BigInteger p[] = new BigInteger [110]; 14 BigInteger P[] = new BigInteger [110]; 15 BigInteger dP[] = new BigInteger [110]; 16 BigInteger M[] = new BigInteger [110]; 17 void init(){ 18 dP[0] = P[0] = p[0] = n0; 19 M[0] = n1; 20 for(int i = 1; i < 102; i++){ 21 //System.out.println(i); 22 p[i] = M[i - 1].multiply(n45); 23 p[i] = p[i].subtract(n9.multiply(P[i - 1])); 24 //System.out.println(p[i]); 25 //System.out.println("ok"); 26 P[i] = p[i].subtract(P[i - 1]); 27 dP[i] = dP[i - 1].add(p[i]); 28 M[i] = M[i - 1].multiply(n10); 29 //System.out.println("M" + i + " " + M[i]); 30 } 31 } 32 33 BigInteger getAns(BigInteger num){ 34 if(num.equals(n0)) return n0; 35 if(num.compareTo(n0) > 0 && num.compareTo(n9) <= 0) return num.add(n1).multiply(num).divide(n2); 36 String str = num.toString(); 37 int len = str.length(); 38 BigInteger first = num.divide(M[len - 1]); 39 BigInteger new_num = num.mod(M[len - 1]); 40 BigInteger tem = dP[len - 1]; 41 //System.out.println("tem" + tem); 42 tem = tem.add(M[len - 1].multiply(first.multiply(first.subtract(n1)).divide(n2))); 43 tem = tem.subtract((first.subtract(n1)).multiply(P[len - 1])); 44 tem = tem.add(new_num.add(n1).multiply(first)); 45 if(new_num.equals(n0)) return tem; 46 BigInteger sign = n1; 47 int tmp = len - 1; 48 while(new_num.divide(M[tmp]).equals(n0)){ 49 tmp--; 50 sign = sign.multiply(rev); 51 } 52 while(new_num.compareTo(n0) > 0){ 53 //System.out.println("tem " + tem); 54 //System.out.println("new_num" + new_num); 55 String new_str = new_num.toString(); 56 int new_len = new_str.length(); 57 BigInteger new_sign = (len - 1) % 2 == 0 ? n1 : rev; 58 int i = 1; 59 //System.out.println("new_len" + new_len); 60 while(i < new_len){ 61 tem = tem.add(new_sign.multiply(p[i])); 62 //System.out.println("i" + i + "p[i]" + p[i] + "tem" + tem); 63 new_sign = new_sign.multiply(rev); 64 i++; 65 } 66 //System.out.println("ok"); 67 //System.out.println("new_sign" + new_sign); 68 BigInteger new_first = new_num.divide(M[new_len - 1]); 69 tem = tem.add(new_first.subtract(n1).multiply(new_first).divide(n2).multiply(M[new_len - 1]).multiply(new_sign)); 70 //System.out.println("tem" + tem); 71 tem = tem.add(new_sign.multiply(rev).multiply(new_first.subtract(n1)).multiply(P[new_len - 1])); 72 //System.out.println("tem" + tem); 73 new_num = new_num.mod(M[new_len - 1]); 74 tem = tem.add(new_first.multiply(n1.add(new_num)).multiply(new_sign)); 75 } 76 return tem; 77 } 78 79 BigInteger f(BigInteger num){ 80 if(num.compareTo(n0) < 0){ 81 BigInteger tem = num.divide(n9); 82 num = num.add(tem.multiply(n9).multiply(rev)); 83 while(num.compareTo(n0) > 0) num = num.subtract(n9); 84 while(num.compareTo(n0) <= 0) num = num.add(n9); 85 } 86 if(num.compareTo(n0) >= 0 && num.compareTo(n9) <= 0) return num; 87 BigInteger tem = n0; 88 while(num.compareTo(n0) > 0){ 89 tem = tem.add(num.mod(n10)); 90 num = num.divide(n10); 91 } 92 return f(tem); 93 } 94 95 void solve(){ 96 Scanner cin = new Scanner(System.in); 97 int T = cin.nextInt(); 98 while(T-- != 0){ 99 String stra = cin.next(); 100 String strb = cin.next(); 101 BigInteger a = new BigInteger(stra); 102 BigInteger b = new BigInteger(strb); 103 BigInteger front = a.equals(n0) ? n0 : getAns(a.subtract(n1)); 104 BigInteger rear = getAns(b); 105 //System.out.println("rear" + rear); 106 BigInteger ans = rear.subtract(front); 107 BigInteger fAns = f(ans); 108 if(fAns.equals(n0)) System.out.println("Error!"); 109 else{ 110 // System.out.println("ans" + ans); 111 //System.out.println("fAns" + fAns); 112 ans = ans.mod(fAns).add(fAns).mod(fAns); 113 System.out.println(ans); 114 } 115 } 116 cin.close(); 117 } 118 public static void main(String[] args) throws IOException{ 119 Main e = new Main(); 120 e.init(); 121 e.solve(); 122 } 123 }