← 返回题目列表

Codeforces · 1264/F

F. 美丽的斐波那契问题

中文机器翻译题面 查看原题

众所周知的斐波那契数列 $$$F_0, F_1, F_2,\ldots $$$ 定义如下:

- $$$F_0 = 0,F_1 = 1$$$。
- 对于每个$$$i \geq 2$$$:$$$F_i = F_{i - 1} + F_{i - 2}$$$。

给定具有 $$$n$$$ 元素的正整数的递增算术序列:$$$(a, a + d, a + 2\cdot d,\ldots, a + (n - 1)\cdot d)$$$。

您需要找到另一个具有 $$$n$$$ 元素 $$$(b, b + e, b + 2\cdot e,\ldots, b + (n - 1)\cdot e)$$$ 的正整数递增算术序列,使得:

- $$$0 < b, e < 2^{64}$$$,
- 对于所有 $$$0\leq i < n$$$,$$$a + i \cdot d$$$ 的十进制表示形式作为子字符串出现在 $$$F_{b + i \cdot e}$$$ 的十进制表示形式的最后 $$$18$$$ 数字中(如果该数字的位数少于 $$$18$$$,则我们考虑其所有数字)。

输入

第一行包含三个正整数 $$$n$$$、$$$a$$$、$$$d$$$ ($$$1 \leq n, a, d, a + (n - 1) \cdot d < 10^6$$$)。

输出

如果不存在这样的算术序列,则打印$$$-1$$$。

否则,打印两个整数 $$$b$$$ 和 $$$e$$$,在一行中用空格分隔 ($$$0 < b, e < 2^{64}$$$)。

如果有多个答案,则可以输出其中任何一个。

示例

输入 #1

3 1 1

输出 #1

2 1

输入 #2

5 1 2

输出 #2

19 5

注意

在第一个测试用例中,我们可以选择$$$(b, e) = (2, 1)$$$,因为$$$F_2 = 1, F_3 = 2, F_4 = 3$$$。

在第二个测试用例中,我们可以选择 $$$(b, e) = (19, 5)$$$ 因为:

- $$$F_{19} = 4181$$$ 包含 $$$1$$$;
- $$$F_{24} = 46368$$$ 包含 $$$3$$$;
- $$$F_{29} = 514229$$$ 包含 $$$5$$$;
- $$$F_{34} = 5702887$$$ 包含 $$$7$$$;
- $$$F_{39} = 63245986$$$ 包含 $$$9$$$。