#P3307. Smart Sister
Smart Sister
题目描述
正在撰写一份报告,因疲惫而小憩。他的妹妹 进入房间后,发现报告中包含许多大整数。她讨厌大数字,于是设计了一种压缩表示方法:
. 数字乘积变换:将一个数的各位数字相乘,得到新数,重复此过程直至结果为个位数(如 )。
. 生产力属性:若某数 可通过其他数的数字乘积变换得到,则称 具有生产力属性(如 、、 均可从 变换得到)。
. 替换规则:将报告中所有具有生产力属性的数 ,替换为它在生产力属性数列中的序号 (按升序排列)。
现在 需要根据妹妹替换后的序号 ,还原原始数字 。
输入格式
第一行:测试用例数量 ( 可达数千)。
接下来 行:每行一个正整数 ,表示 Kamelia 替换后的序号。
输出格式
对每个 ,输出对应的最小原始数字 (保证 )。
样例输入 1
4
10
1
40
11
样例输出 1
10
1
80
12
样例解释
. :生产力属性数列中第 个数是 (因为 无法由其他数乘积变换得到)。
. :数列中第 个数是 (,但 无生产力属性,故 自身是合法最小解)。
. :第 个数是 ()。
. :第 个数是 (,类似 的情况)。
关键思路
. 预处理生产力属性数列:
生成所有能通过数字乘积变换得到的数,并按升序排列。
使用优先队列(最小堆)和哈希表去重,依次生成候选数。
. 映射查询:建立序号 到原始数字 的映射表,直接输出结果。
来源
Amirkabir University of Technology Local Contest