题解：CF1029D Concatenated Multiples

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

a_i\times 10^d+a_j

其中

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

。

注意到其对

k

取模后等价于：

(a_i\times 10^d \bmod k)+(a_j\bmod k)

左右两边互不影响，可以对于每一个数字枚举

d

预处理左边扔进桶里。

然后将每个数字代入右边，算出

d

后在桶里进行查询即可。

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

做完了。

CPP

#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;
}

题解：CF1029D Concatenated Multiples

文章操作

相关推荐

评论

题解：CF1029D Concatenated Multiples