题解 | #被 7 整除#

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // dp[i][j]: 长度为i的数字中余数为j的个数
    vector<vector<int>> dp(10, vector<int>(7, 0));
    // cnt[i]: 余数为i的数字总个数
    vector<int> cnt(7, 0);
    // num[i]: 10的i次方
    vector<int> num(10, 10);
    
    // 预处理10的幂
    for(int i = 1; i < 10; ++i) {
        num[i] = 10 * num[i-1];
    }
    
    int n;
    cin >> n;
    
    // 处理每个输入的数字
    for(int i = 0; i < n; ++i) {
        int v;
        cin >> v;
        // 计算数字长度
        int len = 0;
        while(v / num[len]) ++len;
        // 计算对7的余数
        int mod = v % 7;
        ++cnt[mod];
        ++dp[len][mod];
    }
    
    // 计算结果
    long long res = (cnt[0]-1) * cnt[0];  // 处理余数为0的情况
    
    // 处理其他余数的情况
    for(int i = 1; i < 7; ++i) {
        if(cnt[i] == 0) continue;
        for(int x = 0; x < 10; ++x) {
            for(int y = 0; y < 7; ++y) {
                if(dp[x][y] == 0) continue;
                // 检查拼接后是否能被7整除
                if((i * num[x]) % 7 == (7 - y) % 7) {
                    if(i == y) {
                        res += (cnt[i]-1) * dp[x][y];
                    } else {
                        res += cnt[i] * dp[x][y];
                    }
                }
            }
        }
    }
    
    cout << res << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // dp[i][j]: 长度为i的数字中余数为j的个数
        int[][] dp = new int[10][7];
        // cnt[i]: 余数为i的数字总个数
        int[] cnt = new int[7];
        // num[i]: 10的i次方
        int[] num = new int[10];
        num[0] = 10;
        
        // 预处理10的幂
        for(int i = 1; i < 10; ++i) {
            num[i] = 10 * num[i-1];
        }
        
        int n = sc.nextInt();
        
        // 处理每个输入的数字
        for(int i = 0; i < n; ++i) {
            int v = sc.nextInt();
            // 计算数字长度
            int len = 0;
            while(v / num[len] > 0) ++len;
            // 计算对7的余数
            int mod = v % 7;
            ++cnt[mod];
            ++dp[len][mod];
        }
        
        // 计算结果
        long res = (long)(cnt[0]-1) * cnt[0];  // 处理余数为0的情况
        
        // 处理其他余数的情况
        for(int i = 1; i < 7; ++i) {
            if(cnt[i] == 0) continue;
            for(int x = 0; x < 10; ++x) {
                for(int y = 0; y < 7; ++y) {
                    if(dp[x][y] == 0) continue;
                    // 检查拼接后是否能被7整除
                    if((i * num[x]) % 7 == (7 - y) % 7) {
                        if(i == y) {
                            res += (long)(cnt[i]-1) * dp[x][y];
                        } else {
                            res += (long)cnt[i] * dp[x][y];
                        }
                    }
                }
            }
        }
        
        System.out.println(res);
    }
}

def solve():
    # dp[i][j]: 长度为i的数字中余数为j的个数
    dp = [[0] * 7 for _ in range(10)]
    # cnt[i]: 余数为i的数字总个数
    cnt = [0] * 7
    # num[i]: 10的i次方
    num = [10] * 10
    
    # 预处理10的幂
    for i in range(1, 10):
        num[i] = 10 * num[i-1]
    
    n = int(input())
    nums = list(map(int, input().split()))
    
    # 处理每个输入的数字
    for v in nums:
        # 计算数字长度
        length = 0
        while v // num[length] > 0:
            length += 1
        # 计算对7的余数
        mod = v % 7
        cnt[mod] += 1
        dp[length][mod] += 1
    
    # 计算结果
    res = (cnt[0]-1) * cnt[0]  # 处理余数为0的情况
    
    # 处理其他余数的情况
    for i in range(1, 7):
        if cnt[i] == 0:
            continue
        for x in range(10):
            for y in range(7):
                if dp[x][y] == 0:
                    continue
                # 检查拼接后是否能被7整除
                if (i * num[x]) % 7 == (7 - y) % 7:
                    if i == y:
                        res += (cnt[i]-1) * dp[x][y]
                    else:
                        res += cnt[i] * dp[x][y]
    
    print(res)

solve()