蓝桥杯训练

P8712 [蓝桥杯 2020 省 B1] 整数拼接 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解：这道题和牛客类似，我们换一个思路

我们可以开一个二维数组   一位用来记录拼在后面数的长度，一个用来记录这个数乘上10的（后面数的长度）模10

我们直接乘1到10，全部记录下来

然后枚举右边的数，看看左边有没有数和他对应即可

如果右边模出来等于0  那么和他对应的数就是     左边乘上右边的位数的10次方模k     等于0或者k 就对了

或者模出来是一个数 那么这个数加左边摸出来的数要刚好等于k就对了

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+10,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
int kmp(int a,int k,int p)
{
    int ans=1;
    while (k)
    {
        if(k&1) ans=ans*a%p;
        k>>=1;
        a=a*a;
    }
    return ans;
}
int a[N];
int s[11][N];
int n,k;
void solve()
{

    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int j=1;j<10;j++)
    {
        for(int i=1;i<=n;i++)
        {
            int ans=(int)(pow(10,j)*a[i])%k;
            s[j][ans%k]++;
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        string sp= to_string(a[i]);
        int si=sp.size();
        int op=a[i]%k;
        if(op==0)
        {
            sum+=s[si][0];
            sum+=s[si][k];
        }
        else
        {
            sum+=s[si][k-op];
        }
        if(((int)pow(10,si)*a[i]%k+a[i]%k)%k==0) sum--;
    }
    cout<<sum<<endl;
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}