P8712 [蓝桥杯 2020 省 B1] 整数拼接

https://www.luogu.com.cn/problem/P8712
这题想多了一步。。不需要求逆元，因为最多9位数，所以直接 \(O(10n)\) 记录乘积的模值
注意不能用map

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 1e5 + 5;
ll a[N], b[N], n, k, cnt, a0;
ll pw[15];

int main () {
    pw[0] = 1;
    for (int i = 1; i < 15; i++)   pw[i] = pw[i-1] * 10;
    scanf ("%lld%lld", &n, &k);
    unordered_map<ll, int> mp[15];
    for (int i = 1; i <= n; i++) {
        scanf ("%lld", &a[i]);
        b[i] = to_string (a[i]).size ();
        a[i] %= k;
        for (int j = 0; j <= 10; j++)    mp[j][pw[j]%k*a[i]%k]++;
    }    
    //for (int i = 1; i <= n; i++)    cout << a[i] << ' ' << b[i] << endl;
    for (int i = 1; i <= n; i++) {
        cnt += mp[b[i]][(k-a[i])%k];
        if ((pw[b[i]] % k * a[i] + a[i] % k) % k == 0)    cnt --;
    }
    printf ("%lld\n", cnt);
    return 0;
}

//mod k == 0
//(bx+a)%k=0
//bx=k-a(mod k)
//x=(k-a)*bb (mod k)
//求逆元的时候注意特判0

//费马小定理求逆元只适用于模数是质数
//不要求逆元！！！！