整数拼接（参照acwing的yxc）
整数拼接
给定一个长度为 n 的数组 A1,A2,⋅⋅⋅,An。
你可以从中选出两个数 Ai 和 Aj(i 不等于 j)，然后将 Ai 和 Aj 一前一后拼成一个新的整数。
例如 12 和 345 可以拼成 12345 或 34512。
注意交换 Ai 和 Aj 的顺序总是被视为 2 种拼法，即便是 Ai=Aj 时。
请你计算有多少种拼法满足拼出的整数是 K 的倍数。
输入格式
第一行包含 2 个整数 n 和 K。
第二行包含 n 个整数 A1,A2,⋅⋅⋅,An。
输出格式
一个整数代表答案。
数据范围
1≤n≤105,
1≤K≤105,
1≤Ai≤109
输入样例：
4 2 1 2 3 4输出样例：
6代码1：（超时）
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; public class Main { static int N=100010; static long a[]=new long[N]; // static int res[]=new int[N]; //qq public static void main(String []args) throws IOException{ //System.out.println(1); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); //int n=Integer.parseInt(br.readLine()); String g[]=br.readLine().split(" "); int n=Integer.parseInt(g[0]),k=Integer.parseInt(g[1]); g=br.readLine().split(" "); for (int i = 0; i < n; i++) { a[i]=Long.parseLong(g[i]); } int res=0; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { long a1=a[i],a2=a[j]; BigInteger b1=new BigInteger(a1+""+a2),b2=new BigInteger(a2+""+a1); if(b1.mod(BigInteger.valueOf(k)).equals(BigInteger.ZERO)){ res++; } if(b2.mod(BigInteger.valueOf(k)).equals(BigInteger.ZERO)){ res++; } } } System.out.println(res); } }代码2：
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N=100010; static int a[]=new int[N]; static int s[][]=new int[11][N]; //qq public static void main(String []args) throws IOException{ //System.out.println(1); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); //int n=Integer.parseInt(br.readLine()); String g[]=br.readLine().split(" "); int n=Integer.parseInt(g[0]),k=Integer.parseInt(g[1]); g=br.readLine().split(" "); for (int i = 0; i < n; i++) { a[i]=Integer.parseInt(g[i]); } //(A × 10^lenB + B) mod k = 0等价于： (A × 10^lenB) mod k = (-B) mod k //等价于： (A × 10^lenB) mod k = (k-B) mod k //开一个哈希表 第k个哈希表表示 aj*10^k %k 等于对应值 的个数 k为b的位数 //这样当b固定到时候 只需要去len(b)的哈希表里去找需要的余数就可以了 for (int i = 0; i < n; i++) { int t=a[i]%k; for (int j = 0; j < 11; j++) { s[j][t]++; t=t*10%k; } } long res=0; for (int i = 0; i < n; i++) {//当固定一个b int t=a[i]%k; int len= (a[i]+ "").length(); res+=s[len][(k-t)%k]; //但是也有可能是自己拼自己 算一下是不是 是的话减去1 int r=t; while(len>0){ r=r*10%k; len--; } if(r==(k-t)%k)res--; } System.out.println(res); } }