# CodeForces 1562B Scenes From a Memory

Author: Fanyi Pu

Published: 2021-08-27

Canonical: <https://pufanyi.com/blog/oi-icpc/codeforces/cf1562b>

CodeForces 1562B Scenes From a Memory 题解。

有 $T\,(1\le T\le 10^3)$ 组数据，每组给一个长度为 $k\,(1\le k\le 50)$ 的十进制正整数 $n$，其中 $n$ 在十进制下不存在 $0$（同样不存在前导 $0$），让你求一个整数 $m$，使得 $m$ 在十进制下为 $n$ 在十进制下的子序列，且 $m$ 为**非素数**（$1$ 也是非素数）。子序列不要求连续。

窝萌考虑尽量批量解决一些能解决数。

考虑到如果一个数字含有 $1, 4, 6, 8, 9$，那么这个数只要保留这一位即可，而其余情况均需保留两位。

如果没有这些数，也就是只有 $2, 3, 5, 7$，如果存在两个数字相同，那么只要保留这两个数字就一定被 $11$ 整除，于是位数大于等于 $5$ 位的数字都解决了。

然后考虑到只要 $2$ 和 $7$、$5$ 和 $7$ 在一起，那么取这两个数就一定被 $3$ 整除，于是 $4$ 位数也解决了。

然后如果 $2$ 和 $5$ 不放在第一位，那么就可以整出一个尾数是 $2$ 或尾数 $5$ 的两位数，分别被 $5$ 和 $2$ 整除。

也就是说现在窝萌还不能解决的应该是个三位数，又因为 $2$ 和 $5$ 至少会有一个数被选进这个三位数（$2, 3, 5, 7$ 四个数里选三个嘛），所以 $7$ 就不能来了，这样 $2, 3, 5$ 一定要进场，但是 $2$ 和 $5$ 又都要在开头，所以是不可能的。

于是窝萌发现其实两位及以上的数字窝萌都只需要上面说的 $4$ 个特判就可以了。

总结一下，先判有没有 $1, 4, 6, 8, 9$，如果没有看有没有同时出现 $2$ 和 $7$、$5$ 和 $7$，如果还没有，那我看一下有没有不放在开头的 $2$ 和 $5$。这样就能覆盖到所有可行的数字了。