http://codeforces.com/contest/1029/problem/D
看C题的第一眼就觉得自己一定能做出来，结果就兴致勃勃地做了一天，最后做出来了。但看到这道题时，第一感觉就是“好难啊，我肯定做不出来，而且还是数学题，我从没做出过一道数学题”，默念1分钟丧气话，1分钟后正式放弃了。
我很惊讶，1天的时间不能让我放弃，1分钟却让因为刚通过C题十分兴奋的我放弃了，我觉得自己很神奇= =。然后我就打算，先不管过不过得了，一天之后再放弃，然后我第二天早上就过了……
目标是：O（n）
让我们先举个例子：a1、a2、a3、mod。把a1放在字符串最右边，a2、a3放在字符串左边，那么左边的字符串的余数的贡献是确定的，当a1%mod==0时，find=0，否则find=mod-a1%mod
我们要做的就是把a2、a3扩大a1.length（）后的余数提前处理出来，在遍历的时候查找有没有值等于find。设b[len][n]，第一个下标是a数组所有出现的长度，第二个下标是把a0~an-1全部扩大第一个下标后%mod的值。遍历时，直接找b[ai_len][]里有几个值等于find，累加结果
但我们的b[ai_len][]里包含了ai本身，也就是我们计算了（a1+“”+a1）%mod的情况，因为这种情况的贡献为1，到最后减去就可以了
还有溢出的问题，用bigInteger解决
当b为二维数组时，会有这样的情况 b[1]={1，1，1，1，1}。如果1==find，那么我们要计算所有1的数量，于是我把b变成HashMap类型，key是值，value是个数，这样就可以直接计算了
1 import java.math.BigInteger;
2 import java.util.*;
3
4 public class A {
5 public static void main(String[] args) {
6 Scanner io = new Scanner(System.in);
7 int n = io.nextInt(), a = io.nextInt();
8 BigInteger bigA = new BigInteger(a + "");
9 long[] b = new long[n];
10 int[] c = new int[n];
11 long[] pow = new long[15];
12 String[] pow2 = new String[15];
13 HashSet<Integer> set = new HashSet<>();
14 pow[0] = 1;
15 pow2[0] = "";
16 for (int i = 1; i < pow.length; i++) {
17 pow[i] = pow[i - 1] * 10;
18 pow2[i] = pow2[i - 1] + "0";
19 }
20 long ans = 0;
21
22 for (int i = 0, t; i < n; i++) {
23 t = io.nextInt();
24 b[i] = t % a;
25 c[i] = (t + "").length();
26 set.add(c[i]);
27 }
28
29 HashMap<Long, Long>[] map = new HashMap[pow.length];
30 for (int l : set) {
31 map[l] = new HashMap();
32 for (int i = 0; i < n; i++) {
33 long m = (1L * (b[i] % a) * pow[l] % a);
34 if (m < 0) {
35 BigInteger big = new BigInteger(b[i] + pow2[l]);
36 m = big.mod(bigA).longValue();
37 }
38 map[l].put(m, map[l].getOrDefault(m, 0L) + 1);
39 }
40 }
41
42 for (int i = 0; i < n; i++) {
43 long find = b[i] == 0 ? 0 : a - b[i];
44 if (!map[c[i]].containsKey(find)) continue;
45 long cnt = map[c[i]].get(find);
46 long t = 1L * (b[i] % a) * pow[c[i]] % a;
47 if (t < 0) {
48 BigInteger big = new BigInteger(b[i] + pow2[c[i]]);
49 t = big.mod(bigA).longValue();
50 }
51 //减去（a1+“”+a1）%mod的贡献
52 if (t == find) cnt--;
53 ans += cnt;
54 }
55 System.out.println(ans);
56 }
57 }