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

問題概要

正整数 $n$ ， $k$ と， $n$ 個の正整数 $a$ が与えられる． $a_i$ と $a_j$ を連結させた数のうち， $k$ で割り切れるペア $(i, j)$ の個数を答えよ．ただし $i \neq j$ ．連結させた数の例としては， $a_j = 12$ と $a_i = 654$ なら $12654$ ． $a_j = 487$ と $a_i = 3$ なら $4873$ とする．

解法パートで， $a_j$ と $a_i$ を連結させた数を $a_j a_i$ という風に書く．

解法

$a_i$ を，mod $k$ で $0$ にしたいと考える． $a_i$ に $k - a_i$ を足したら，mod $k$ で $0$ になる．正整数 $a_i$ は高々 $2 \times 10^5$ 個あるので，一つの $a_i$ に対して条件を満たす $k - a_i$ が何個あるかを高速に求めたい．

ここで， $d(a_i)$ を $a_i$ の桁数とする． $d(12) = 2$ ， $d(12345678) = 8$ と言った感じ．こうすると， $a_j$ と $a_i$ を固定し， $a_j a_i$ という連結させた数が $a_j \times 10^{d(a_i)} + a_i$ と表せる．例えば， $a_j = 57$ ， $a_i = 332$ とすると， $d(332) = 3$ であって $57332 = 57 \times 10^3 + 332$ と書ける．

上のように書いて何がうれしいかと言うと，和の前と後でバラバラにmodを取れることである．つまり， $(a_j \times 10^{d(a_i)} \% k)+ (a_i \% k)$ というように計算できる．上の例では， $k = 11$ とすると $57332 \% 11 = ( (57 \times 10^3) \% 11 + (332 \% 11) ) \% 11 = (2 + 9) \% 11 = 11 \% 11 = 0$ となる．

最初にしたかったことを思い出す．一つの $a_i$ に対して条件を満たす $k - a_i$ が何個あるかを高速に求めたい．前処理として， $(a_j \times 10^{d(a_i)} \% k)$ を取り得る $d(a_i)$ に対してすべて計算し，何個あるかカウントしておくと最初にしたかったことができる．

$d(a_i)$ が取り得る値の範囲を考える．こういうときは制約を見返すとよくて， $1 \le a_i \le 10^9$ である．したがって， $a_i$ は高々 $10$ 桁にしかならないので， $1 \le d(a_i) \le 10$ である．

このようにして各 $a_j$ に対して， $(a_j \times 10^{d(a_i)} \% k)$ を $1 \le d(a_i) \le 10$ の範囲ですべて計算してから個数カウントする前処理をした後で，各 $a_i$ ごとに $k - a_i$ の個数を足し合わせたら，答えが求まる．

TLが2secだとギリギリだったり， $(k - a_i)$ と $a_i \times 10^{d(a_i)}$ が同じになるとき（これをカウントしてしまうと $a_i$ と $a_i$ のペアを数えることになる）に注意しながら実装する．

実装

コード

// #define _GLIBCXX_DEBUG
// #pragma GCC optimize("Ofast")
#pragma GCC diagnostic ignored "-Wsign-compare"
#include <bits/stdc++.h>
// #include <atcoder/all>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define reps(i, s, n) for (int i = s; i < (int)(n); ++i)
using namespace std;
using ll = long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
constexpr int INF = 1e9 + 7;
constexpr ll LINF = 1LL << 60;

int calc_digit(ll a) {
    int ret = 0;
    while (a > 0) {
        ret++;
        a /= 10;
    }
    return ret;
}

void solve() {
    ll n, k;
    cin >> n >> k;
    V<ll> A(n);
    rep(i, n) cin >> A[i];

    VV<ll> val(11, V<ll>(n));
    rep(i, n) {
        ll v = A[i];
        rep(d, 11) {
            val[d][i] = v;
            v *= 10;
            v %= k;
        }
    }
    map<ll, ll> cnt[11];
    rep(d, 11) {
        rep(i, n) { cnt[d][val[d][i]]++; }
    }
    ll ans = 0;
    rep(i, n) {
        int d = calc_digit(A[i]);
        ll need = (k - A[i] % k) % k;  // A[i] % k = 0のときがあるので，外側でも % kする
        ans += cnt[d][need];
        if (need == val[d][i]) ans--;
    }
    cout << ans << "\n";
}
int main() {
    cin.tie(nullptr);
    // ios_base::sync_with_stdio(false);
    // cout << fixed << setprecision(15);
    solve();
}