题解：CF1029D Concatenated Multiples

fish_love_cat · 2025-07-07 16:41:30 · 题解

首先拼接后的数字可以表示成：

其中 d=\lfloor \log_{10}a_j \rfloor+1。

注意到其对 k 取模后等价于：

左右两边互不影响，可以对于每一个数字枚举 d 预处理左边扔进桶里。

然后将每个数字代入右边，算出 d 后在桶里进行查询即可。

注意桶要用 __gnu_pbds::cc_hash_table<int,int>。

做完了。

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
using namespace std;
__gnu_pbds::cc_hash_table<int,int>mp[15];
int a[200005],b[200005],c[200005];
int ans;
signed main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        int g=a[i];
        while(g){
            b[i]++;
            g/=10;
        }
        // cout<<b[i]<<' ';
        for(int j=10%k,e=1;e<=10;e++,j=j*10%k){
            mp[e][a[i]%k*j%k]++;
            if(b[i]==e)c[i]=a[i]%k*j%k;
        }
        a[i]%=k;
    }
    for(int i=1;i<=n;i++)
    ans+=mp[b[i]][(k-a[i])%k]-((k-a[i])%k==c[i]);
    cout<<ans;
    return 0;
}