题目描述

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

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

例如 12 和 345 可以拼成 12345 或 34512。

注意交换 Ai 和 Aj 的顺序总是被视为 2 种拼法，即便是 Ai=Aj 时。

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

输入输出

输入格式
第一行包含 2 个整数 n 和 K。

第二行包含 n 个整数 A1,A2,⋅⋅⋅,An。

输出格式
一个整数代表答案。

数据范围
1≤n≤10^5,

1≤K≤10^5,

1≤Ai≤10^9

时间复杂度

nlogn

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long LL;

const int N=100010;

int n,k;
int a[N];
int s[11][N]; //s[i][j]存储乘以10^i后，余数为j的整数个数

/*
    假设拼接后的数字是 aj*（10^ki）+ai ,（ki是ai的位数）
    aj*（10^ki）+ai能整除k, 说明 aj*（10^ki）mod k == -ai mod k
    也就是 aj*（10^ki）mod k +ai mod k = k*（0或1）
*/

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0; i<n; i++)  scanf("%d",&a[i]);

    LL t;
    for(int i=0; i<n; i++)  // 预处理每个数成员10^(0~10) mod m 的结果
    {
        t=a[i] % k;
        for(int j=0; j<11; j++)
        {
            s[j][t]++;
            t=t*10 % k; // t=a[i]*10 % k的值
        }
    }

    LL res=0;
    for(int i=0; i<n; i++)
    {
        t=a[i] % k;
        int len=to_string(a[i]).size();
        res+=s[len][(k-t) % k];  
        //这里k-t 还要 mod k的原因是，当t=0时，拼接的另一个数 mod k =0 而不是=k

        /*
        当拼接的另一个数是自己的时候要去掉一种答案,只会减一，
        所以即使是有两个相同的拼接数，也不会有影响，只会减去自己拼自己的一种答案
        */
        int r=t;
        while(len--)  r=r*10 % k;
        if(r == (k-t) % k)  res--;
    }
    printf("%lld",res);
    return 0;
}