#P3307. Smart Sister

    ID: 2308 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>难度入门Amirkabir University of Technology Local Contest 2006指针

Smart Sister

题目描述

KamranKamran 正在撰写一份报告,因疲惫而小憩。他的妹妹 KameliaKamelia 进入房间后,发现报告中包含许多大整数。她讨厌大数字,于是设计了一种压缩表示方法:
11. 数字乘积变换:将一个数的各位数字相乘,得到新数,重复此过程直至结果为个位数(如 9729×7×2=1261×2×6=121×2=2972 → 9×7×2=126 → 1×2×6=12 → 1×2=2)。
22. 生产力属性:若某数 xx 可通过其他数的数字乘积变换得到,则称 xx 具有生产力属性(如 126126121222 均可从 972972 变换得到)。
33. 替换规则:将报告中所有具有生产力属性的数 xx,替换为它在生产力属性数列中的序号 ii(按升序排列)。

现在 KamranKamran 需要根据妹妹替换后的序号 ii,还原原始数字 xx

输入格式

第一行:测试用例数量 TTTT 可达数千)。
接下来 TT 行:每行一个正整数 ii,表示 Kamelia 替换后的序号。

输出格式

对每个 ii,输出对应的最小原始数字 xx(保证 x<1018x < 10^{18})。

样例输入 1

4
10
1
40
11

样例输出 1

10
1
80
12

样例解释

11. i=1i=1:生产力属性数列中第 11 个数是 11(因为 11 无法由其他数乘积变换得到)。
22. i=10i=10:数列中第 1010 个数是 1010101×0=010 → 1×0=0,但 00 无生产力属性,故 1010 自身是合法最小解)。
33. i=11i=11:第 1111 个数是 1212121×2=212 → 1×2=2)。
44. i=40i=40:第 4040 个数是 8080808×0=080 → 8×0=0,类似 1010 的情况)。

关键思路

11. 预处理生产力属性数列
生成所有能通过数字乘积变换得到的数,并按升序排列。
使用优先队列(最小堆)和哈希表去重,依次生成候选数。
22. 映射查询:建立序号 ii 到原始数字 xx 的映射表,直接输出结果。

来源

Amirkabir University of Technology Local Contest 20062006