被 7 整除

被7整除的数

暴力做法时间复杂度O(NN), 2 <= n <= ,会超时。

暴力做法： 枚举第一个数x, 再枚举第二个数y,拼接两个数， bit(y) 表示y是几位数。

因此，得到的新数是：，
我们在暴力算法基础上优化算法。
我们又知道，A % 7 = a, B % 7 = b，如果(a+b) % 7 == 0，则一定有 % 7 等于0。

为了降低复杂度我们可以先预处理出来所有数是几位数，% 7 余 几。每位数都是1位数到10位数，因此可以直接从表中查出当前数和1-10位数拼接，并且想要拼接的这个数%7 余几。

import java.util.*;
public class Main {
    static int getBit(int t) { // 计算该为数字为几位数
        int cnt = 0;
        while(t > 0) {cnt++; t /= 10;}
        return cnt;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[][] bit = new int[11][7]; //计数,【x是几位数】【x mod 7】
        for(int i=0; i < n; i++) {
            a[i] = sc.nextInt();
            bit[getBit(a[i])][a[i] % 7]++; 
        }
        long res = 0L; 
        for(int i=0; i < n; i++) {
            int x = a[i] % 7, y = getBit(a[i]);
            bit[y][x] --; // 当前数先刨除在外
            long num = (long)a[i];
            for(int j=1; j <= 10; j++) {
                num = num * 10;
                int re = (int)(num % 7); // A mod 7 的余数
                res = res + bit[j][(7 - re) % 7]; //直接查找
            }
            bit[y][x] ++; // 恢复
        }
        System.out.println(res);
    }
}