题目描述

blablabla

给定一个长度为 n 的数组 A1,A2,⋅⋅⋅,An。

你可以从中选出两个数 Ai 和 Aj(i 不等于 j)，然后将 Ai 和 Aj 一前一后拼成一个新的整数。

请你计算有多少种拼法满足拼出的整数是 K 的倍数。

算法1

(哈希表) $O(n)$

思路：哈希表myhash[11][100007];
左边方括号为拼接位数，右边为mod k的余数
myhash[i][j]的值为后面拼接位数为i（乘i个10），mod k余j的数目
求解此myhash复杂度O（11n）~O（n）
在上面求myhash过程中注意考虑a[i][j]拼接a[i][j]的情况，要剔除。
a[i]拼接a[j]mod k为0，即a[i]乘a[j]个10+a[j]%k==0
即a[i]乘a[j]个10%k==-a[j]%k
然后遍历所有元素，算出-a[j]%k，
求和myhash[a[j]位数][-a[j]%k]，即可得到

C++ 代码

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
typedef long long ll;
ll myhash[11][100007];
//左边方括号为拼接位数，右边为mod k的余数
//myhash[i][j]的值为后面拼接位数为i（乘i个10），mod k余j的数目
/*在上面求myhash过程中注意考虑a[i][j]拼接a[i][j]的情况，要剔除。
a[i]拼接a[j]mod k为0，即a[i]乘a[j]个10 + a[j] % k == 0
即a[i]乘a[j]个10 % k == -a[j] % k
然后遍历所有元素，算出 - a[j] % k，
求和myhash[a[j]位数][-a[j] % k]，即可得到*/
ll a[100007];
ll GetWei(ll num) //获取一个数的位数
{
    int sum = 0;
    while (num > 0) {
        sum++;
        num = num / 10;
    }
    return sum;
}
int main()
{
    ll n, k;
    ll temp;
    ll temp_yushu = 0;
    ll sum = 0;
    ll wei;
    scanf("%lld", &n);
    scanf("%lld", &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);  //a[]存放题目给的数
    }
    for (int i = 1; i <= n; i++) {
        wei = GetWei(a[i]);  //得到a[i]的位数
        temp = a[i] % k;     //计算a[i]%k余下的值
        myhash[0][temp]++;  //拼接位数为0,余数为temp的元素数目加一
        for (int j = 1; j <= 10; j++) {  //最多乘10^10
            temp = temp * 10 % k; //计算余数
            myhash[j][temp]++;   
            if (j == wei) {  //剔除a[i][j]拼接a[i][j]的情况
                temp_yushu = -a[i] % k;
                if (temp_yushu < 0) {
                    temp_yushu = temp_yushu + k;
                }
                if (temp == temp_yushu) {
                    sum--;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        temp_yushu = -a[i] % k;  //与这个数同余
        if (temp_yushu < 0) {
            temp_yushu = temp_yushu + k;
        }
        sum += myhash[GetWei(a[i])][temp_yushu];//累加
    }

    printf("%lld", sum);
    return 0;
}