2021 软件学院 AK 杯程序设计竞赛 (现场赛)

Problem J. 白茶与数位之积

果冻挑战成功,去了异世界开发手游。临走前,他撕毁了条约,公开了私藏未销毁的锦乐照片。在发现照片公开的瞬间,白茶的 AI 立马监测到了,并打算在发布到网上之前将其拦截。拦截需要解出果冻加密用的自创数位积算法,破解具体如下:

对于非负整数 kk,定义 f(k)f(k) 为十进制下 kk 的所有数位的乘积,如:

f(27)=2×7=14f(365)=3×6×5=90 \begin{aligned} f(27)&= 2 \times 7=14 \\ f(365)&= 3 \times 6 \times 5= 90 \end{aligned}

现给定非负整数 x,yx,y,试找到一个有序对 (l,r)(l,r),满足 l,rl,r 都是整数,且有:

0lr10y1x=i=lrf(i)=f(l)×f(l+1)×f(l+2)××f(r1)×f(r) 0\leq l \leq r \leq 10^y -1 \\ x=\prod_{i=l}^{r}{f(i)}=f(l) \times f(l+1) \times f(l+2) \times \cdots \times f(r-1) \times f(r)

输入

输入包含多组测试用例。

第一行包含一个整数 t (1t2×104)t \ (1 \leq t \leq 2 \times 10^4),表示你需要处理 tt 组测试用例。

接下来 tt 行每行一组测试用例,各包含两个用空格间隔的整数 x,y (0x1018,0y18)x,y \ (0 \leq x \leq 10^{18},0 \leq y \leq 18),含义如题目描述所示。

输出

对于每组测试用例,如果存在符合题目条件的有序对,输出两个整数 l,rl,r,表示你找到的有序对,如果有多个符合题目条件的有序对,你只需要输出其中任意一个;如果不存在符合题目条件的有序对,输出 1-1

数与数之间用空格或换行符间隔。

样例

标准输入 复制文本
4
120 5
97 12
1000000000 18
0 18
标准输出 复制文本
14 16
-1
252525252525252525 252525252525252525
0 0

提示

对于测试用例 11i=1416f(i)=120\prod_{i=14}^{16}{f(i)}= 120,且 0141610510 \leq 14 \leq 16 \leq 10^5 -1,故 (14,16)(14,16) 符合题意。

对于测试用例 22,可以证明一定不存在符合条件的有序对,故输出 1-1

对于测试用例 33,注意有些符合条件的 l,rl,r 不一定能用整型变量储存。

测试用例 1,3,41,3,4 的答案均不唯一。

登录以提交代码。
单点时限 2 秒
内存限制 512 MB
提交 8
通过 1

A B C D E F G H I J

赛后 17:10 将于三楼机房进行题解讲解。
G 题输入描述有更新,请刷新页面查看。