题解：AT_abc433_d [ABC433D] 183183

kuaiCreator · 2025-11-30 11:46:32 · 题解

思路

将函数转化为 f(A_i,A_j)\bmod M=(A_i\times 10^{d}+A_j) \bmod M=0 其中 d=\lfloor\log_{10}A_j\rfloor +1。

暴力枚举 i,j 会超时。

进一步转化 (A_i\times 10^{d}\bmod M+A_j\bmod M) \bmod M=0。

令 r_1=A_i\times 10^{d}\bmod M,r_2=A_j\bmod M。

考虑 A_j 确定时，r_2 确定进一步可以算出 r_1。则若能统计 A_i\times 10^{d}\bmod M 余数为 r_2 的个数，累加给答案即可。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<pair<int, int>, int> mp;
ll n, m, ans, base[15], a[200005], l[200005];
int cal(int n) {
    int len = 0;
    do {
        len++;
        n /= 10;
    } while (n);
    return len;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    base[0] = 1;
    for (int i = 1; i <= 10; i++) base[i] = base[i - 1] * 10;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        l[i] = cal(a[i]);
        for (int d = 1; d <= 10; d++) {
            int r = a[i] % m  * base[d] % m;
            mp[make_pair(d, r)]++;
        }
    }
    for (int i = 1; i <= n; i++) {
        int r = (m - a[i] % m) % m;
        ans += mp[make_pair(l[i], r)];
    }
    cout << ans;
    return 0;
}