思路

先从暴力角度出发
两个for循环找到每一个可以与a[i]匹配的数
但是时间复杂度为O(n^2)

那么如何优化?
第一层枚举a[i]是肯定不行的，那么就找如何快速找到和a[i]匹配的数
这里涉及到关于模的运算的知识

(a[j]10^len(a[i]) + a[i]) % k === 0;
可以转化为: (a[j]10^len(a[i]) % k === -a[i] % k;

因为k的数据范围不是很大只有1e5，并且a[i]的数位<=10
那么可以将a[j]的每一个10^i % k的数存入一个二维数组里面

二维数组：s[11][N]表示对于a[j]*10^(0-10) % k 的数有多少个
然后用 -a[i] % k 来取出这些数

那么如何表示一个负数的模呢?
res = ((负数 % mod) + mod) % mod;
把负数的负号提出来 -> (mod - (num % mod)) % mod

还有一个问题
因为在预处理数据的时候一定会枚举到自己。
将自己本身 ✖ 10的j次方 % k存入到s数组中，所以在计算res的时候要判断一下

$O(nlogn)$

C++ 代码

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

const int N = 1e5+10;
typedef long long ll;
int n,k;
int a[N];
int s[11][N];

int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
        int t = a[i] % k;
        for(int j = 0; j < 11; j ++)
        {
            // 把a[i]对于每个10^j的余数存入哈希表里面
            s[j][t] ++;
            t = t * 10 % k;
        }
    }
    ll res = 0;
    for(int i = 0; i < n; i ++)
    {
        int t = a[i] % k;
        int len = to_string(a[i]).size();
        // 找到和 -a[i] % k 相等的a[j]*10^len(a[i]) % k
        res += s[len][(k - t) % k];

        ll r = t;
        // 如果a[j] == a[i] 那么 res--
        while(len --) r = r * 10 % k;
        if(r == (k - t) % k) res --;
    }

    cout << res << endl;

    return 0;
}