【蓝桥杯】整数拼接

思路分析： 根据题意可推出，A与B拼接可以推出等式 A + 10^x^ + B，题目可以翻译成是求A + 10^x + B % K == 0的个数。首先我们肯定不能去枚举两重循环，这样必定会超时（不过比赛时不会最优解可以骗分，可以拿一半以上的分）， 我们通过观察等式A + 10^x^ + B % K == 0进行等价变形，变成(A + 10^x) % K = - B % K，并且B与x正相关，则我们可以用一个哈希表存起来A + 10x，用空间换时间，那么我们的两重循环就可以换成一个只枚举A，调用哈希只需要O(1)的时间，到现在看来题目就迎刃而解了，本题时间复杂度为O(n)。

补充：-B % K == (K - (B % K)) % K（感兴趣的话百度了解一下）

```
#include
using namespace std;
const int N = 100010;
typedef long long ll;
ll a[N],hash_table[11][N];
int main()
{
    int n,k;
    cin >> n >> k;
    for (int i = 0; i < n; i ++ )
    {
        cin >> a[i];
        ll t = a[i] % k;
        for (int j = 0 ; j < 11; j ++ )
        {
            hash_table[j][t] ++ ;
            t = t * 10 % k;
        }
    }
    ll res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int len = to_string(a[i]).size();
        res += hash_table[len][(k - (a[i] % k)) % k];
        
        ll t = a[i] % k;
        while(len -- ) t = t * 10 % k;
        if(t % k == (k - (a[i] % k)) % k ) res --; //判重 如果查找到的值包括自己，减掉自己
    }
    cout<<res<<endl;
    return 0;
}