题目描述

算法1

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

typedef long long LL;
const int N=100010;

int n,m;
int a[N],s[11][N];

//主要思想就是，对于模m的情况。
//把和的前半部分维护为 乘以不同权重情况下，模数相同的个数。
//再枚举和的后半部分，O(1)的和当前情况相匹配的数的个数。
//注意自己和自己匹配不符合题意，要特判减去。

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

    for(int i=0;i<n;i++)
    {
        LL t=a[i]%m;
        for(int j=0;j<11;j++)
        {
            s[j][t]++;      //表示，乘10的j次方后，模m为t的数的个数。
            t=t*10%m;
        }
    }

    LL res=0;
    for(int i=0;i<n;i++)
    {
        LL t=a[i]%m;
        int len = to_string(a[i]).size();
        res += s[len][(m-t)%m];

        //注意，自己和自己不能拼接，要减去这种特殊情况
        LL r=t;
        while(len--) r=r*10%m;
        if(r==(m-t)%m) res--;

    }

    printf("%lld\n",res);

    return 0;
}