抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

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

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

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

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

然后考虑到只要 22 和 77、55 和 77 在一起,那么取这两个数就一定被 33 整除,于是 44 位数也解决了。

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

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

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

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

评论