被 7 整除

import java.util.Scanner;

// for for 会超时, 需预处理
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] cnt = new int[11][7]; // cnt[i][j]表示 i位数num%7=j 的数字个数
        long[] base = new long[11]; // base[i]=10^i
        base[0] = 1;
        for (int i = 1; i <= 10; i++) {
            base[i] = base[i - 1] * 10;
        }
        while (n-- > 0) {
            int num = in.nextInt();
            int bit = 0, mod = num % 7;
            while (num > 0) {
                bit++;
                num /= 10;
            }
            bit = (bit == 0) ? 1 : bit;
            cnt[bit][mod]++;
        }

        long res = 0;
        for (int i1 = 1; i1 <= 10; i1++) {
            for (int j1 = 0; j1 < 7; j1++) {
                for (int i2 = 1; i2 <= 10; i2++) {
                    for (int j2 = 0; j2 < 7; j2++) {
                        if ((j1 * base[i2] + j2) % 7 == 0) {
                            if (i1 == i2 && j1 == j2) {
                                res += cnt[i1][j1] * (cnt[i1][j1] - 1);
                            } else {
                                res += cnt[i1][j1] * cnt[i2][j2];
                            }
                        }
                    }
                }
            }
        }
        System.out.println(res);
    }
}

被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);
    }
}