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
//费马小定理求逆元只适用于模数是质数
//不要求逆元！！！！