蓝桥杯省赛B组 整数拼接

### 题目链接 [acwing2068. 整数拼接](https://www.acwing.com/problem/content/description/2070/) ### 题目大意 现在已知一个长度为 $n$ 的数组 $A$ ,现从 $A$ 中任取取两个数拼成一个整数(显然有两种拼法),现在问能拼出的所有整数中有多少是 $k$ 的倍数。 ### 思路 蓝桥杯的省赛就这么难吗，呜呜呜我好菜啊，想了半天（真·半天）才有思路... 直接 $O(n^2)$ 暴力枚举所有情况肯定是不行的，那么我们就来考虑拼出来的数字能被 $k$ 整除和用来拼的这两个数有什么联系： 1. 首先，两个数都被 $k$ 整除拼成一个数字是一定能被 $k$ 整除的 2. 如果后面那个数（假设为 $A_j$ ）不能被 $k$ 整除，那么前面那个数乘上 $10^{lenA_j}$ 对 $k$ 取余数加上 $A_j \% k$ 是 $k$ 的倍数才能被 $k$ 整除。 3. 其他情况均不能被 $k$ 整除。 其实，第二种情况是包含第一种情况的，因此，假设选出的前面那个数为 $A_i$ ，后面那个数为 $A_j$ ，那么可以得到满足条件： $$ (A_j\%k+A_i\%k\times 10^{lenA_j})\%k==0 $$ 下面就是考虑如何提高效率了，我们注意到 $lenA_i$ 可能的取值只有 $1\to 10$ 十种情况，因此如果预处理出所有数字乘 $10$ 的 $1$ 到 $10$ 次方对 $k$ 取模的值，统计一下每种值的个数，就可以在计算 $A_j$ 作为后面那个数的时候直接得到数量为 $v[len(A_j)][(k-(A_j\%k))\%k]$ ( $v[i][j]$ 表示的是满足 $\times 10^i$ 的对 $k$ 取模余数是 $j$ 的数字个数)。 但是这里还有一个问题就是前后两数不同，但是很多情况下会把自己算在里面，因此可以再开一个数组记录自己和自己拼接是否也能被 $k$ 整除，计算过程中或者最后减掉即可。 ### code ``` cpp #include <cstdio> using namespace std; const int maxn = 1e5 + 7; long long n, k, a[2][maxn], v[11][maxn], num[2][maxn], ans; inline int getdig(long long x) { int ansx = 0; while (x) x /= 10, ++ansx; return ansx; } int main() { scanf("%lld%lld", &n, &k); for (int i = 1; i <= n; ++i) scanf("%lld", &a[0][i]), a[1][i] = a[0][i] % k, ++v[0][a[1][i]], num[0][i] = getdig(a[0][i]); for (int i = 1; i <= n; ++i) for (long long j = 1, o = a[1][i]; j <= 10; ++v[j][o = ((o << 1) + (o << 3)) % k], ++j) if (j == num[0][i]) num[1][i] = (o + a[0][i]) % k == 0; for (int i = 1; i <= n; ++i) ans += v[num[0][i]][(k - a[1][i]) % k] - num[1][i]; printf("%lld", ans); return 0; } ```