C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

枚举 哈希表

1、$假设从数组中取出的两个数：a_i, a_j$

2、$题目要求a_i, a_j拼接所形成的数是k的倍数的个数$

3、$a_j a_i = a_j*10^{k_i} + a_i$

4、$a_j* 10 ^ {len} == -a_i(mod\ k)$

$开11个哈希表：$

$0：a_j*10^0$

$1：a_j*10^1$

$2：a_j*10^2$
···

$10：a_j*10^10$

$第k_i个哈希表中：-a_i$

$时间复杂度：O(nlogn)$

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
typedef long long ll;

int n, k;
int a[N], s[11][N];

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i ++) cin >> a[i];

    // 预处理哈希表
    for (int i = 0; i < n; i ++) { // 枚举每个数
        ll t = a[i] % k;
        for (int j = 0; j < 11; j ++) { // 枚举t的 10^j 次方
            s[j][t] ++;
            t = t * 10 % k;
        }
    }

    ll res = 0;
    for (int i = 0; i < n; i ++) {
        ll t = a[i] % k;
        int len = to_string(a[i]).size(); // 看一下a[i]的位数
        res += s[len][(k - t) % k];

        ll r = t;
        while (len --) r = r * 10 % k; // 判重
        if (r == (k - t) % k) res --; 
        /*
        当我们所枚举的这个数a[i]乘上10^len == -a[i]
        表明我们此时所取出的两数是一个数，不符合题目要求
        */
    }
    cout << res;

    return 0;
}