loj#P2328. 「清华集训 2017」避难所
「清华集训 2017」避难所
题目描述
“B君啊,你当年的伙伴都不在北京了,为什么你还在北京呢?”
“大概是因为出了一些事故吧,否则这道题就不叫避难所了。”
“唔,那你之后会去哪呢?”
“去一个没有冬天的地方。”
对于一个正整数 ,我们定义他在 进制下,各个位上的数的乘积为 。
比如 。
考虑这样一个问题,已知 和 ,求最小的 满足 。
这是一个非常有趣的问题,对于一些 来说,我们可以贪心来做,比如如果 。
我们可以从 到 试除,直到 为 为止,答案是 ,可以验证 是满足 最小的 。
但是对于一些进制 ,是不能用贪心做的,比如 。使用贪心得到的解是 ,而最优解是 。(均为 进制下的。)
本题便是在给定进制 的情况下,举出一个这样的反例,或指出这样的反例不存在。
由于计算资源所限,反例中所有数字的乘积不能超过 。如果最小的反例中所有数字的乘积超过了 ,那么也应该输出 。
输入格式
从标准输入读入数据。
第一行一个整数 ,表示一共有 组数据。
接下来每行一个整数 ,表示进制。
输出格式
输出到标准输出。
如果不存在反例,输出一行一个整数 。
如果存在反例,首先输出一个整数 ,表示反例 的位数,接下来在同一行输出 个十进制整数,表示任意一个反例的最优解。
3
8
9
10
-1
3 6 6 6
-1
数据范围与提示
对于第 个测试点,分值为 ,;
对于第 个测试点,分值为 ,;
对于第 个测试点,分值为 ,。