原题链接

详情参考博客 整数拼接

题目描述：
给定一个长度为 n的数组 A~1~,A~2~,⋅⋅⋅,A~n~。你可以从中选出两个数 A~i~和 A~j~(i不等于 j)，然后将 A~i~和 A~j~一前一后拼成一个新的整数。例如 12和 345可以拼成 12345或 34512。注意交换 A~i~ 和 A~j~的顺序总是被视为 2 种拼法，即便是 A~i~=A~j~时。请你计算有多少种拼法满足拼出的整数是 k的倍数。

输入格式：

第一行包含 2 个整数n和 k。第二行包含 n个整数 A~1~,A~2~,⋅⋅⋅,A~n~

输出格式：

一个整数代表答案

数据范围：

1 <= n <= 10^5^
1 <= k <= 10^5^
1 <= A~i~ <= 10^9^

输入样例：

4 2
1 2 3 4

输入样例：

6

思路分析：首先A~i~与A~j~拼接成的数为：A~i~*10^x^+A~j~或A~j~*10^y^+A~i~，==其中x = A~j~的长度，y = A~j~的长度==。如12和345拼接 = 12*10^3^+345或者345*10^2^+12。而一个数是k的倍数，则这个数 mod k = 0。因此(A~i~*10^x^+A~j~) mod k = 0 或者（A~j~*10^y^+A~i~）mod k =0。那么这道题最直接简单的办法就是两层循环暴力枚举，找到满足条件的两个数，代码如下：

  for(int i=0;i<n;i++)   //枚举其中两个数，不能为同一个数
    {
        for(int j=i+1;j<n;j++)
        {
            if(((A[i]%k*power(digit_len(A[j]))%k)+A[j])%k==0)
            {
                res++;
            }
            if(((A[j]%k*power(digit_len(A[i]))%k)+A[i])%k==0)//交换顺序
            {
                res++;
            }
        }
    }
// power(x)是返回10的x次方，digit_le是返回一个数的长度

==上述代码时间复杂度为O(n^2^)，数据量为10^5^，因此会出现超时，所以该方法不可取==。为了减少时间复杂度我们应该修改等式 (A~i~*10^x^+A~j~) mod k = 0。
这里我们令 a = A~i~*10^x^，b = A~j~则原等式等价于 (a+b) mod k = 0，根据取模运算的规则，a+b一定是k的某个倍数，故 a + b = n*k，因此 a = n*k - b，现在对两边取模运算得$$a \% k = -b\%k$$ 因为n*k%k=0，那么我们将A~i~和A~j~带入这个式子得公式（1）$$A~i~*10^x\%k = -A~j~\%k （1） $$
==注意：在数学规定中，取模运算最后的答案一定是正数，而在计算机编程中-A~j~ % k则会是个负数，下面代码会出现左边为正数，右边为负数，那么永远不会出现等于的情况==

if(A[i]*10*power(digit_len(A[j])) %k== -A[j]%k)
    res++;

因此需要进一步转换公式，将等式右边的值计算到正数，我们知道k-a%k 与-a同余，即(k-a%k)%k = -a%k。根据模运算的传递性，若a mod k =b mod k，b mod k = c mod k，则 a mod k = c mod k
因此 -A~j~%k 可以改为(k-A~j~%k) %k （==其中k-A~j~%k与-A同余，如-7 mod 3 = 2，而 (3 -7 mod 2) mod 3 = (3-1) mod 3 = 2，模运算优先级高于加减法==）因此公式进一步改写为公式（2）$$A~i~*10^x\%k = (k-A~j~\%k)\%k（2）$$有了这个公式之后，我们只需要建立一个哈希表，提前把数组中的乘以10的某个次方 mod k 的值存入一个二维数组，这里我们建立数组s[11][N]，第一个下标表示乘以10的多少次方，根据题目数据，最多不会超过11次，第二个下标表示乘以10的某个次方后对k取模的值。==比如s[2][100] = 3表示有数列中有3个数*10^2^ mod k = 100，这里我们假设这三个数分别是A~i~，A~j~，A~k~，这个时候我们遍历整个数组若能找到某个A~t~，且根据上面的公式（2），若(k-A~t~%k）%k\=100，在满足公式（2），即认为A~i~,A~j~,A~k~都能与A~t~组成一个是k的倍数的数，那么我们让答res+=s[2][100]，即我们认为找到了三个符合答案的组合，但注意，由于我们会提前对哈希数组进行预处理，所以A~t~一定是A~i~，A~j~，A~k~中的某个数，即t一定等于i、j、k中的一个数，故A~i~,A~j~,A~k~可以两两组合成为一个答案，共六种答案，这个时候res+=s[2][100]执行3次，（当t=i、j、k时各执行一次，）结果得出了9个答案，这是由于出现了某个数自己拼接自己导致的。根据题意由于某个数不能和自己拼接成为一个答案，因此我们需要进行去重。==

代码部分：

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

int digit_len(long long num) // 返回num有多少位
{
    int len = 0;
    while (num > 0)
    {
        len++;
        num /= 10;
    }
    return len;
}

long long power(int idx) // 返回10的idx次方
{
    long long res = 1;
    while (idx--)
    {
        res *= 10;
    }
    return res;
}

const int N = 1e5 + 10;
long long s[11][N]; /* cnt[i][j]表示某个数乘以10的i次方%k = j 的数量，存储的结果表示有几个数可以互相组合*/

int main()
{
    int n, k;
    int A[N];
    long long res = 0;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    // 预处理哈希表
    for (int i = 0; i < n; i++) // 依次计算数组中所有数乘以10的某个次方对k取模的余数,这样就能判断是否能满足上述等式中的左右同余
    {
        long long m = A[i] % k;
        for (int j = 1; j < 11; j++) // 依次乘以10的1到10次方
        {
            m = m * 10 % k;
            s[j][m]++;
        }
    }
    // 遍历数组，累加答案
    for (int i = 0; i < n; i++)
    {
        long long t = A[i] % k;
        long long x = (k - t) % k; // 计算（k-A[i]%k)%k
        int len = digit_len(A[i]); // 获得A[i]的长度
        res += s[len][x];

        // // 判重
        t = t * power(len) % k; // 计算A[i]*10^len%k
        if (t == x) //表示A[i]*10^len%k=(k-A[i]%k)%k，说明一定多加了一次自己拼自己的结果
        {
            // 因为自己不能和自己拼，这个A[i]一定在预处理环节中计算到哈希数组中去了
            res--;
        }
    }
    cout << res;
    return 0;
}

if (t == x) 表示A[i]*10^len^%k=(k-A[i]%k)%k，说明一定多加了一次自己拼自己的结果，因为比如有A~i~、A~j~、A~k~、三个数字都能互相组合，而哈希表在预处理中会保存3，那么在代码运算中会多计算3次自己拼自己的结果，因此在遍历A~i~，A~j~，A~k~三个数的时候，都需要分别去一次重，哪怕三个数的值相等也没关系，每次遍历最多去一次重