AT_abc433_d

jojo222 · 2025-11-30 07:14:57 · 题解

讨厌的 64 位整数，害得我吃了一发罚时。

思路

先开一个 map 数组，mp_{i} 代表一个数（数组中）补 i 个零后模 m 为 j 的方案数。

接着再枚举每一个数。显然一个数补 \operatorname{len}(a_i) 个零后再加 a_i 就是最终的数。加后是 m 的倍数，加前模 m 为 m-a_i\bmod m。因此对答案的贡献是 mp_{\operatorname{len}(a_i),m-a_i\bmod m}。

核心代码

ll n, m, ans, a[200005];
map<int, int> mp[15];
int main()
{
    read(n, m), readArr(a, n);
    ull x = 1;
    rep(i, 1, 10)
    {
        x *= 10;
        rep(j, 1, n) mp[i][1ull * a[j] * x % m]++;
    }
    rep(i, 1, n) ans += mp[int(log10(a[i])) + 1][(m - a[i] % m) % m];
    write(ans);
    return 0;
}