Codeforces Round #506 (Div. 3)(D

链接：https://codeforces.com/contest/1029/problem/D
思路：题目要求任选两个不相同数按照字符串形式拼起来后，能被k整除，求一共有多少组。首先我们不可能真的把他拼起来再去算，而且n的范围告诉我们我们只能枚举一个数，个数要在O（1）时间内求出，那么我们自然而然想到枚举这个每个数字后面拼1-9位时他的余数，用一个map记录某位数余数位某个数时的数字的个数，然后查询即可。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,k;
const int maxn = 2e5+100;
int a[maxn];
map<int,int> jj[15]; //map<余数,数目> jj[位数]
int num[maxn];
long long res = 0;

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        int now = a[i];
        while(now>0){
            now/=10;
            num[i]++;
        }
        jj[num[i]][a[i]%k]++;//位数位num[i]余数位a[i]%k的数个数+1
    }
    for(int i=1;i<=n;i++){
        long long base = 1,now = 0;
        for(int j=1;j<=10;j++){
            base*=10;
            now = ((base%k)*(a[i]%k))%k;
            res+=jj[j][(k-now)%k];//查询位数为j且余数为(k-now)%k的数有多少个
            if(j==num[i]&&(now%k+a[i]%k)%k==0)res--;    //如果对应相等，则他自己也被算了一次，要在这里扣除
        }
    }   
    printf("%I64d\n",res);
    return 0;
}