D. Concatenated Multiples

숫자가 n개 주어지고 이중 두개를 연결시켰을 때 k로 나누어떨어지게 하는 숫자쌍의 수를 구하는 문제다.

1. 숫자를 입력받은 후에 pow(10, i)를 곱하면서 %k한 것을 vector[i]에 저장한다. 입력은 10^9까지이므로 i는 10까지

2. 각각의 숫자를 다시 돌아보면서 자리수 rad를 계산해서 ((k - self%k)%k + target)%k == 0 인 target을 이분탐색으로 찾는다. 여러개 있을 수 있기 때문에 upper_bound, lower_bound를 찾아야 한다.

3. ub~lb에 자신도 있다면 1을 빼준다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
typedef long long ll;
ll n, k, ans;
ll a[200001];
ll po[11];
vector<ll> aa[11];
 
ll rad(ll x) {
    ll ans = 0;
    while (x) {
        ans++;
        x /= 10;
    }
    return ans;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    po[0] = 1;
    for (int i = 1; i < 11; ++i)
        po[i] = po[i - 1] * 10;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ll mm = 1;
        for (int j = 0; j < 11; ++j) {
            aa[j].push_back(((mm%k)*(a[i]%k)) % k);
            mm *= 10;
        }
    }
    for (int i = 0; i < 11; ++i)
        sort(aa[i].begin(), aa[i].end());
    for (int i = 0; i < n; ++i) {
        ll r = rad(a[i]);
        ll t = (k - (a[i]%k))%k;
        ans += upper_bound(aa[r].begin(), aa[r].end(), t) - lower_bound(aa[r].begin(), aa[r].end(), t);
        if (t == ((a[i]%k) * (po[r]%k)) % k) 
            ans--;
    }
    cout << ans;
    return 0;
}