Codeforces Round #506 (Div. 3) D Concatenated Multiples (cf 1029D)

题目：Concatenated Multiples

题意：给出$n$个数，求数对$(x,y)$的个数，使得$a_x$和$a_y$简单拼接后能被$k$整除。

思路：
对于两个数$x$和$y$，简单拼接后能被$k$整除，当且仅当 $x×10^{log_{10}y+1} mod \ k \ +\ y\ mod \ k\ ==\ 0$
所以可以预处理出每个数$a_i$后填上$j$个$0$除k的余数x，用$map$存储添$j$个$0$余数为$x$的数的个数，计作$mp[j][x]$。
预处理完，就再对于每个数查询满足上述条件的数的个数，加入答案中。
注意当一个数自己和自己拼接可以被k整除时要特殊判断下。

代码：

#include<bits/stdc++.h>
using namespace std;#define ll long long
#define inf (1<<30)
#define maxn 200000int n,k;
int a[maxn+5];map<int,int> mp[15];void read(int& x) {scanf("%d",&x);
}int main() {read(n);read(k);for(int i=1;i<=n;i++) {read(a[i]);ll x=a[i];for(int j=1;j<=10;j++) {x*=10;x%=k;mp[j][x]++;}}ll ans=0;for(int i=1;i<=n;i++) {int len=log10(a[i])+1;ans+=mp[len][(k-a[i]%k)%k];ll x=1;for(int j=1;j<=len;j++) x=x*10%k;if(((x*a[i])%k+a[i]%k)%k==0) ans--;}printf("%I64d",ans);return 0;
}