#P1900. 自我数

自我数

题目背景

#题目有加强

题目描述

在 1949 年印度数学家 D. R. Daprekar 发现了一类称作 Self-Numbers 的数。对于每一个正整数 nn,我们定义 d(n)d(n)nn 加上它每一位数字的和。例如, d(75)=75+7+5=87d(75) = 75 + 7 + 5 = 87。给定任意正整数 nn 作为一个起点,都能构造出一个无限递增的序列:n,d(n),d(d(n)),d(d(d(n))),n, d(n), d(d(n)), d(d(d(n))), \ldots 例如,如果你从 3333 开始,下一个数是 33+3+3=3933 + 3 + 3 = 39,再下一个为 39+3+9=5139 + 3 + 9 = 51,再再下一个为 51+5+1=5751 + 5 + 1 = 57,因此你所产生的序列就像这样:$33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, \ldots$。数字 nn 被称作 d(n)d(n) 的发生器。在上面的这个序列中,33333939 的发生器,39395151 的发生器,51515757 的发生器等等。有一些数有超过一个发生器,如 101101 的发生器可以是 9191100100。一个没有发生器的数被称作 Self-Number。如前 1313 个 Self-Number 为 1,3,5,7,9,20,31,42,53,64,75,86,971, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97。我们将第 ii 个 Self-Number 表示为 aia_i,所以 a1=1,a2=3,a3=5,a_1 = 1, a_2 = 3, a_3 = 5, \ldots

输入格式

输入包含整数 N,K,s1,,sKN, K, s_1, \ldots, s_K,其中 1N1071 \le N \le {10}^71K50001 \le K \le 5000,以空格和换行分割。

输出格式

在第一行你需要输出一个数,这个数表示在闭区间 [1,N][1, N] 中 Self-Number 的数量。第二行必须包含以空格划分的 KK 个数,表示 as1,,asKa_{s_1}, \ldots, a_{s_K},这里保证所有的 as1,,asKa_{s_1}, \ldots, a_{s_K} 都小于 NN。(例如,如果 N=100N = 100sks_k 可以为 1131 \sim 13,但不能为 1414,因为 a14=108>100a_{14} = 108 > 100

100 10
1 2 3 4 5 6 7 11 12 13 

13
1 3 5 7 9 20 31 75 86 97

提示

对于 100%100 \% 的数据,1N1071 \le N \le {10}^71K50001 \le K \le 5000