A20984.自我数
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
#题目有加强
在 1949 年印度数学家 D. R. Daprekar 发现了一类称作 Self-Numbers 的数。对于每一个正整数 n,我们定义 d(n) 为 n 加上它每一位数字的和。例如, d(75)=75+7+5=87。给定任意正整数 n 作为一个起点,都能构造出一个无限递增的序列:n,d(n),d(d(n)),d(d(d(n))),… 例如,如果你从 33 开始,下一个数是 33+3+3=39,再下一个为 39+3+9=51,再再下一个为 51+5+1=57,因此你所产生的序列就像这样:33,39,51,57,69,84,96,111,114,120,123,129,141,…。数字 n 被称作 d(n) 的发生器。在上面的这个序列中,33 是 39 的发生器,39 是 51 的发生器,51 是 57 的发生器等等。有一些数有超过一个发生器,如 101 的发生器可以是 91 和 100。一个没有发生器的数被称作 Self-Number。如前 13 个 Self-Number 为 1,3,5,7,9,20,31,42,53,64,75,86,97。我们将第 i 个 Self-Number 表示为 ai,所以 a1=1,a2=3,a3=5,…。
输入格式
输入包含整数 N,K,s1,…,sK,其中 1≤N≤107、1≤K≤5000,以空格和换行分割。
输出格式
在第一行你需要输出一个数,这个数表示在闭区间 [1,N] 中 Self-Number 的数量。第二行必须包含以空格划分的 K 个数,表示 as1,…,asK,这里保证所有的 as1,…,asK 都小于 N。(例如,如果 N=100,sk 可以为 1∼13,但不能为 14,因为 a14=108>100)
输入输出样例
输入#1
100 10 1 2 3 4 5 6 7 11 12 13
输出#1
13 1 3 5 7 9 20 31 75 86 97
说明/提示
对于 100% 的数据,1≤N≤107,1≤K≤5000。