Concatenated Multiples

Created by LXC on Wed Jul 26 00:24:34 2023

https://codeforces.com/problemset/problem/1029/D

ranting: 1900

tag: implementation, math

problem

给出n个数的数组a，求任意两个数$a_i$和$a_j$（$i\ne j$）在拼接后是k的倍数的数对$(i,j)$的个数。

$1\le n\le 2\cdot 10^5, 1 \le a_i \le 10^9, 2 \le k \le 10^9$

solution

设$a_i$的10进制位数为$len_i$
$a_i$和$a_j$拼接后的值是$a_i\cdot10^{len_{a_j}}+a_j$，所以如果拼接后是k的倍数，那么$a_i\cdot10^{len_{a_j}}$除以k的余数加上$a_j$除以k的余数是k或者是0。

预处理出$r_{i,j}$为10进制长度为i且除以k的余数是j的个数。可以用10个平衡树作为存储结构。

可以枚举每个数$a_i$在其后拼接长度为j的数，拼接后的一部分值为$a_i\cdot10^j$，很容易求出它除以k的余数，设余数为t，我们需要求在a中有多少个长度为j的数且除以k的余数为k-t或0，显然为$r_{j,k-t}$。

值得注意的是拼接的两个数是在a中下标不可以相同，但在这里我们计算进去了。所以当$a_i$和$a_i$拼接后是k的倍数，则需要将答案减少1

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n, k;
    cin >> n >> k;
    vector<ll> len(n), a(n);
    map<int, int> r[11];

    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        a[i] = x;
        while (x)
            len[i]++, x /= 10;
        r[len[i]][a[i] % k]++;
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll x = a[i];
        for (int j = 1; j < 11; j++) {
            x *= 10;
            x %= k;
            ll t = (k - x) % k;
            if (r[j].count(t))
                ans += r[j][t];
            if (len[i] == j && (x + a[i] % k) % k == 0)
                ans--;
        }
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}