当前没有测试数据。

P7960 [NOIP2021] 报数 完整题目信息

题目描述

报数游戏是一个广为流传的休闲小游戏。在标准规则下，参加游戏的人需要按顺序轮流报数，但如果遇到 7 的倍数 或 十进制表示中含有数字 7 的数，就必须跳过这个数，否则输掉游戏。

小 z 对游戏进行了加强：任何一个十进制中含有数字 7 的数，它的所有倍数都不能报出来！

形式化地，设 $p(x)$ 表示 $x$ 的十进制表示中是否含有数字 $7$，若含有则 $p(x) = 1$，否则 $p(x) = 0$。则一个正整数 $x$ 不能被报出，当且仅当存在正整数 $y$，使得 $x$ 是 $y$ 的倍数且 $p(y)=1$。

现在给定 $T$ 次询问，每次询问给出一个正整数 $x$：

• 若 $x$ 是不能报出的数，输出 -1
• 若 $x$ 是合法的数，输出 严格大于 $x$ 的最小合法数（即小 z 接下来要报的数）

输入格式

• 第一行：一个正整数 $T$，表示询问次数
• 接下来 $T$ 行：每行一个正整数 $x$，表示每次询问的数

输出格式

• 共 $T$ 行，每行一个整数，为对应询问的答案

样例输入 1

4
6
33
69
300

样例输出 1

8
36
80
-1

样例解释 1

• 询问 6：6 是合法数，下一个合法数是 8（7 含数字 7，被跳过）
• 询问 33：33 合法，34（含 7）、35（含 7）均不合法，下一个是 36
• 询问 69：69 合法，70–79 均含 7，下一个合法数是 80
• 询问 300：$300 = 75 \times 4$，75 含数字 7，因此 300 不合法，输出 -1

样例输入 2

5
90
99
106
114
169

样例输出 2

92
100
109
-1
180

数据范围与约定

• 对于 $10\%$ 的数据：$T \le 10,\ x \le 100$
• 对于 $30\%$ 的数据：$T \le 100,\ x \le 1000$
• 对于 $50\%$ 的数据：$T \le 1000,\ x \le 10^4$
• 对于 $70\%$ 的数据：$T \le 10^4,\ x \le 2 \times 10^5$
• 对于 100% 的数据：$\boldsymbol{1 \le T \le 2 \times 10^5,\ 1 \le x \le 10^7}$