Submission #71156225

---

Source Code Expand

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

long long pw(long long a, long long b, long long m) {
    long long res = 1;
    a %= m;
    while (b > 0) {
        if (b % 2 == 1) res = (res * a) % m;
        a = (a * a) % m;
        b /= 2;
    }
    return res;
}

int len(long long n) {
    string s = to_string(n);
    return s.length();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    long long m;
    cin >> n >> m;

    vector<long long> a(n);
    vector<long long> v[11];

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        v[len(a[i])].push_back(a[i] % m);
    }

    for (int i = 1; i <= 10; i++) {
        sort(v[i].begin(), v[i].end());
    }

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= 10; j++) {
            if (v[j].empty()) continue;

            long long mul = pw(10, j, m);
            long long cur = (a[i] % m * mul) % m;
            long long tar = (m - cur) % m;

            ans += upper_bound(v[j].begin(), v[j].end(), tar) - lower_bound(v[j].begin(), v[j].end(), tar);
        }
    }

    cout << ans;
    return 0;
}

Submission Info

Judge Result